# Optimal Account Balancing LeetCode Solution

Difficulty Level Hard

## 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.

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

We will be left with three kinds of people

1. People who will get money back (Positive)
2. People who owe money. (Negative)
3. 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] -= t;
bal[t] += t;
}

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;
int taker = transaction;
int amount = transaction;
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}))```

O(E+V)

O(V)

Translate »