LeetCode Solutions Blog

Optimal Account Balancing

Number: 465

Difficulty: Hard

Paid? Yes

Problem Description

Given an array of transactions where each transaction indicates that one person gave a certain amount of money to another, determine the minimum number of transactions required to settle all debts among the persons involved.

Key Insights

Compute the net balance for each person.
Only consider persons with non-zero balance, since persons with a zero net balance do not affect the result.
Use backtracking (DFS) to try settling debts between pairs of people.
Prune redundant operations by skipping similar debt values in subsequent recursive calls.
The problem size is small (max 12 persons and 8 transactions) so a DFS/backtracking solution is practical.

Space and Time Complexity

Time Complexity: O(2^n) in the worst-case scenario, where n is the number of non-zero balances. Space Complexity: O(n) due to recursion and the balance array.

Solution

We first compute each person's net balance. Then, we use a depth-first search (DFS) approach to try and settle each outstanding balance with minimal transactions. In the DFS, we attempt to settle the debt of one person with another by transferring money and recursively exploring the outcome. If a debt is completely settled, we move on to the next balance. To optimize, we skip over redundant operations when we have already tried to settle with a similar debt value. We employ backtracking to restore the original state after trying each settlement possibility. This recursive strategy allows us to explore all combinations while keeping track of the minimum number of transactions required.

Code Solutions

# Python solution for Optimal Account Balancing

def minTransfers(transactions):
    from collections import defaultdict
    # Compute net balance for each person.
    balance = defaultdict(int)
    for frm, to, amount in transactions:
        balance[frm] -= amount  # person gives money
        balance[to] += amount   # person receives money
    
    # Filter out persons with zero balance.
    debts = [amount for amount in balance.values() if amount != 0]
    
    def dfs(start):
        # Skip settled debts.
        while start < len(debts) and debts[start] == 0:
            start += 1
        # All debts settled.
        if start == len(debts):
            return 0
        min_trans = float('inf')
        for i in range(start + 1, len(debts)):
            # Only attempt to settle if debts[start] and debts[i] are opposite in sign.
            if debts[start] * debts[i] < 0:
                # Settle debts[start] with debts[i].
                debts[i] += debts[start]
                # Recurse: 1 transaction is used.
                min_trans = min(min_trans, 1 + dfs(start + 1))
                # Backtrack: restore debts[i].
                debts[i] -= debts[start]
                # Optimization: if debts[i] becomes zero after settlement,
                # no need to try other similar values.
                if debts[i] + debts[start] == 0:
                    break
        return min_trans
    
    return dfs(0)

# Example usage
transactions = [[0,1,10],[2,0,5]]
print(minTransfers(transactions))  # Output: 2