Optimal Account Balancing LeetCode Solution

Table of Contents

Problem Statement

Optimal Account Balancing LeetCode Solution – You are given an array of transactions transactions where transactions[i] = [from_i, to_i, amount_i] indicates that the person with ID = from_i gave amount_i $ to the person with ID = to_i.

Return the minimum number of transactions required to settle the debt.

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Explanation

what does it mean to settle the debt ?

nobody owes others

how do we represent how much money a person owes others?
We build the current debt situation debt[], e.g. debt[i] = 10 means a person owes others 10? how do we settle one’s debt
assuming [0, curId – 1] has been settled,
for debt[curId],
any curId + 1 <= i <debt.length such that debt[i] * debt[curId] < 0 can settle it

state
The next account to balance, curId, can uniquely identify a state
state function
state(debt[], curId) is the minimum transactions to balance debts[curId…debtLength – 1] such that debts[0…curId-1] are balanced.
goal state
state(initial debt[], 0)
state transition
now: state(debt[], curId)
next: state (debt[] after balance curId, curId + 1)

state(debt[], curId) = 1 + min(state (debt[] after balance curId, curId + 1))

Note

How do we decide who can balance the account of curId?
There are many people who can balance curId’s account — person i behind curId with debt[i] * debt[curId] < 0.

We go through every transaction and update the values for each person.

If a person has given money to someone else, he gets back that much money. So we add that money to his account.
If a person owes money, then we deduct the money from his account.

We will be left with three kinds of people

People who will get money back (Positive)
People who owe money. (Negative)
People who neither get back nor owe money. We will ignore these people as they are settled.

Now we need to match the positive amounts with negative amounts. Once all the positives and negatives cancel out, we check the transactions required and we take the minimum.

We do not know the order in which these balances are matched which will yield minimum transactions. So we need to try out all the combinations. We use backtracking/dfs.
We will discard the dfs where the transactions count is greater than the minimum. (Pruning)

Code

C++ Code for Optimal Account Balancing

class Solution {
public:
    int minTransfers(vector<vector<int>>& trans) 
  {
        unordered_map<int, long> bal; // each person's overall balance
        for(auto& t: trans) {
      bal[t[0]] -= t[2];
      bal[t[1]] += t[2];
    }
    
        for(auto& p: bal) // only deal with non-zero debts
      if(p.second) debt.push_back(p.second);
      
        return dfs(0);
    }
    
private:
    int dfs(int s) // min number of transactions to settle starting from debt[s]
  { 
    	while (s < debt.size() && !debt[s]) ++s; // get next non-zero debt
    
    	int res = INT_MAX;
    	for (long i = s+1, prev = 0; i < debt.size(); ++i)
    	  if (debt[i] != prev && debt[i]*debt[s] < 0) // skip already tested or same sign debt
      {
        debt[i] += debt[s]; 
      res = min(res, 1+dfs(s+1)); 
      prev = (debt[i]-=debt[s]);
      }
    	    
    	return res < INT_MAX? res : 0;
    }
    
    vector<long> debt; // all non-zero debts
};

Java Code for Optimal Account Balancing

class Solution {
    public int minTransfers(int[][] transactions) {
        int[] debt = buildDebtArray(transactions); // Debt amount to balance for each person.
        
        return getMinTransfersAfter(0, debt);
    }
    
    private int getMinTransfersAfter(int curId, int[] debt) {
        while (curId < debt.length && debt[curId] == 0)
            curId++;
        // Base case.
        if (curId == debt.length)
            return 0;
        // Recursive case.
        int minTransactions = Integer.MAX_VALUE;
        for (int i = curId + 1; i < debt.length; i++) {
            if (debt[i] * debt[curId] < 0) {
                debt[i] += debt[curId];
                minTransactions = Math.min(minTransactions, getMinTransfersAfter(curId + 1, debt) + 1);
                debt[i] -= debt[curId];
            }
        }
        
        return minTransactions;
    }
    
    private int[] buildDebtArray(int[][] transactions) {
        Map<Integer, Integer> debtMap = new HashMap<>(); // Map person ID to debt amount.
        
        for (int[] transaction : transactions) {
            int giver = transaction[0];
            int taker = transaction[1];
            int amount = transaction[2];
            debtMap.put(giver, debtMap.getOrDefault(giver, 0) + amount);
            debtMap.put(taker, debtMap.getOrDefault(taker, 0) - amount);
        }
        
        int[] debt = new int[debtMap.size()];
        int i = 0;
        for (int amount : debtMap.values()) {
            debt[i++] = amount;
        }
        
        return debt;
    }
}

Python Code for Optimal Account Balancing

class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:

        tuplify = lambda balance: tuple(sorted((k, v) for k, v in balance.items()))

        @lru_cache(None)
        def dfs(balances):
            if not balances:
                return 0
            res = math.inf
            balances = {k: v for k, v in balances}
            for size in range(2, len(balances) + 1):
                for group in itertools.combinations(balances.keys(), size):
                    if sum(balances[k] for k in group) == 0:
                        remaining_balances = {k: v for k, v in balances.items() if k not in group}
                        res = min(res, size - 1 + dfs(tuplify(remaining_balances)))
            return res

        balances = collections.defaultdict(int)
        for u, v, z in transactions:
            balances[u] += z
            balances[v] -= z
        return dfs(tuplify({k: v for k, v in balances.items() if v}))