Optimal Account Balancing - Leetcode Solution

The Optimal Account Balancing problem on LeetCode is a problem where you are given a list of transactions, each transaction being a tuple of three integers (a, b, c), which represents that person 'a' lent person 'b' an amount of 'c' dollars.

The goal is to find the minimum number of transactions required to settle all debts.

Algorithm:

• Create a dictionary where the key is the person's ID, and the value is the net amount of money they owe or are owed after all transactions.
• Convert the dictionary into a list, discarding the people who have a balance of 0.
• Call the helper function dfs with the new list and a starting index of 0, and a variable 'count' initialized to 0.
• In the helper function 'dfs', we iterate through all the people who have a non-zero balance, starting from the 'start' index.
• If two people have opposite sign balances, then a transaction can take place, and we reduce the balances of these people by the transaction amount. We then recursively call the dfs function with the updated list and a new starting index of 'i+1'.
• If all balances are 0, then we return the current count.
• If no transaction takes place in the current iteration, we break the loop and return the current count.

Here's the code:

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        
        # Step 1: Create a dictionary where key is person's ID and value is net amount they owe or are owed after all transactions
        balances = defaultdict(int)
        for from_person, to_person, amount in transactions:
            balances[from_person] -= amount
            balances[to_person] += amount
        
        # Step 2: Convert the dictionary into a list, discarding the people who have a balance of 0
        balance_list = [v for v in balances.values() if v != 0]
        
        # Step 3: Call the helper function dfs with the new list and a starting index of 0, and a variable 'count' initialized to 0
        return self.dfs(balance_list, 0, 0)
    
    
    def dfs(self, balance_list, start, count):
        n = len(balance_list)
        
        # Step 4: Iterate through all the people who have a non-zero balance, starting from the 'start' index
        while start < n and balance_list[start] == 0:
            start += 1
        
        # Step 5: If all balances are 0, then we return the current count
        if start == n:
            return count
        
        # Step 6: For all subsequent non-zero balances, check if a transaction can be made with the current person and any subsequent person who has an opposite sign balance
        for i in range(start+1, n):
            if balance_list[start] * balance_list[i] < 0:
                # A transaction can take place, so reduce the balances of the people involved by the transaction amount
                balance_list[i] += balance_list[start]
                count = self.dfs(balance_list, start+1, count+1)
                # Backtrack by restoring the previous balance values
                balance_list[i] -= balance_list[start]
                
        # Step 7: If no transaction takes place in the current iteration, we break the loop and return the current count
        return count

Complexity Analysis:

• Time Complexity: O(2^N), where N is the number of non-zero balances. Since in the worst case, we will have to consider all combinations of transactions. However, the actual time complexity will be much lower than 2^N, due to the early stopping condition.
• Space Complexity: O(N), where N is the number of non-zero balances. This is because of the recursion stack. However, the actual space used will not be N, as some of the branches will be pruned early.

1