LeetCode 465: Optimal Account Balancing

link

We can summarize all transactions as balances per person. In the end, there might be positive balances and negative balances, but they must sum up to 0.

Blind alleys

If one person has negative balance and two persons have positive balances, those two must pay the person with negative balance. Likewise, if one person has positive balance and two persons have negative balances, that one person must pay to the two persons with negative balances.
- Idea: Let’s return max( positive_balance_count, negative_balance_count ).
- Does not work: [[0,1,5],[2,3,1],[2,0,1],[4,0,2]].
Match positive balances with negative balances.
- Does not work:
  [[0,3,2],[1,4,3],[2,3,2],[2,4,2]]
Match biggest positive with smallest negative.
- Does not work: [[2,0,5],[3,4,4]]
Match biggest positive with biggest negative
- Does not work: [[1,5,8],[8,9,8],[2,3,9],[4,3,1]]
Try matching with most similar negative balance
- Does not work: [[0,1,3],[0,2,3],[3,4,4]]

What works

Try matching each positive balance with each negative balance making sure a transaction does not change a positive balance to negative or a negative balance to positive.

Time: $\mathcal{O}( n^2! )$ , space: $\mathcal{O}(n^2)$ .

from itertools import product as cartesian

class Solution:
    def find_min_transfer_count(self, debts, owes, total_debt, transfer_count) -> int:
        if total_debt == 0:
            return transfer_count
        
        min_transfer_count = float('inf')
        for i, j in cartesian( range(len(debts)), range(len(owes)) ):
            pos = debts[i]
            if pos == 0:
                continue
            neg = owes[j]
            if neg == 0:
                continue
            
            delta = min( pos, -neg )
            debts[i] -= delta
            owes[j] += delta

            min_transfer_count = min(
                min_transfer_count,
                self.find_min_transfer_count(
                    debts, owes, total_debt-delta, transfer_count+1
            )
            )

            debts[i] += delta
            owes[j] -= delta

        return min_transfer_count

    def minTransfers(self, transactions: List[List[int]]) -> int:
        balance_map = {}
        for giver, taker, amount in transactions:
            balance_map[giver] = balance_map.get(giver, 0) - amount
            balance_map[taker] = balance_map.get(taker, 0) + amount
        
        debts = [ b for b in balance_map.values() if b > 0 ]
        if not debts:
            return 0
        
        owes = [b for b in balance_map.values() if b < 0]

        return self.find_min_transfer_count(
            debts,
            owes,
            sum(debts),
            0
        )

Settle current person’s balance with someone later in the sequence regardless the later person’s balance go negative –> positive or positive –> negative. In that way, for each recursive call we are eliminating one person.

Time: $\mathcal{O}(n!)$ , space: $\mathcal{O}(n)$ .

from collections import defaultdict

class Solution:
    def find_min_transfer_count(self, current_index: int, balances: List[int], transfer_count: int) -> int:
        # Make sure current_index has not already been settled by an earlier person
        while current_index < len(balances) and balances[current_index] == 0:
            current_index += 1

        if current_index >= len(balances):
            return transfer_count
        
        min_transfer_count = float('inf')
        for next_index in range(current_index, len(balances)):
            if balances[next_index] == 0:
                continue

            # Settle positive with negative or negative with positive
            if (balances[current_index] > 0) == (balances[next_index] > 0):
                continue
            
            balances[next_index] += balances[current_index]

            min_transfer_count = min(
                min_transfer_count,
                self.find_min_transfer_count(
                    current_index+1,
                    balances,
                    transfer_count+1,
                )
            )

            balances[next_index] -= balances[current_index]
            
        return min_transfer_count

    def minTransfers(self, transactions: List[List[int]]) -> int:
        balance_map = defaultdict(int)
        for giver, taker, amount in transactions:
            balance_map[giver] -= amount
            balance_map[taker] += amount
        
        balances_to_settle = [b for b in balance_map.values() if b != 0]

        return self.find_min_transfer_count(
            0,
            balances_to_settle,
            0,
        )

unreasonably effective