Optimal Account Balancing
Optimal Account Balancing is a hard dynamic programming problem solved with the bitmask dp pattern.
The best approach, optimal (bitmask dp over zero-sum groups), runs in O(2^k · k) time and O(2^k) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (backtracking over who settles with whom) up.
Problem
A group of friends lent each other money. Each entry transactions[i] = [from, to, amount] means person from paid amount to person to on someone’s behalf, so to now owes that much more to from.
Everyone wants to end up even. A single transfer moves any amount of money from one person to another. Return the minimum number of transfers needed so that every person’s total paid equals their total received.
Examples
Example 1
- Input
transactions = [[0, 1, 20], [1, 2, 20]]- Output
1- Why
- Person 1 received 20 and passed 20 on, so they are even. Person 2 simply pays 20 back to person 0.
Example 2
- Input
transactions = [[0, 1, 7], [1, 0, 3], [2, 3, 4]]- Output
2- Why
- Person 1 owes 4 to person 0 and person 3 owes 4 to person 2. The two pairs are independent, so two transfers.
Example 3
- Input
transactions = [[0, 1, 5], [0, 2, 5], [3, 0, 6], [4, 0, 4]]- Output
3- Why
- Person 0 ends even. Persons 1 and 2 owe 5 each, persons 3 and 4 are owed 6 and 4; no smaller group cancels out, so four people need three transfers.
Constraints
1 <= transactions.length <= 8transactions[i] = [from, to, amount]0 <= from, to < 12andfrom != to1 <= amount <= 100
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (backtracking over who settles with whom) | O(k!) | O(k) |
| Optimal (bitmask DP over zero-sum groups) | O(2^k · k) | O(2^k) |
1Brute force (backtracking over who settles with whom)
O(k!)Each level may branch to every later person of opposite sign, so the search tree can grow factorially in the number k of non-zero balances.O(k)The recursion goes at most k levels deep and the balance list has k entries.Reduce the transactions to a list of non-zero balances. Take the first unsettled person and try to settle their entire balance with each later person of the opposite sign: move the balance onto that person, recurse on the rest and undo. The minimum over all choices, plus one for the current transfer, is the answer.
- Compute the balance of every person and keep only the non-zero ones in a list
debt. dfs(start): skip indices withdebt[start] == 0; ifstartreaches the end, return 0.- For each
i > startwithdebt[i] * debt[start] < 0: adddebt[start]todebt[i], take1 + dfs(start + 1), then undo. - Return the minimum found; the answer is
dfs(0).
class Solution {
public int minTransfers(int[][] transactions) {
int[] bal = new int[12];
for (int[] t : transactions) {
bal[t[0]] -= t[2];
bal[t[1]] += t[2];
}
List<Integer> list = new ArrayList<>();
for (int b : bal) if (b != 0) list.add(b);
int[] debt = new int[list.size()];
for (int i = 0; i < debt.length; i++) debt[i] = list.get(i);
return dfs(debt, 0);
}
private int dfs(int[] debt, int start) {
while (start < debt.length && debt[start] == 0) start++;
if (start == debt.length) return 0;
int best = Integer.MAX_VALUE;
for (int i = start + 1; i < debt.length; i++) {
if ((long) debt[i] * debt[start] < 0) {
debt[i] += debt[start];
best = Math.min(best, 1 + dfs(debt, start + 1));
debt[i] -= debt[start];
}
}
return best;
}
}class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
bal = [0] * 12
for f, t, amt in transactions:
bal[f] -= amt
bal[t] += amt
debt = [b for b in bal if b != 0]
def dfs(start: int) -> int:
while start < len(debt) and debt[start] == 0:
start += 1
if start == len(debt):
return 0
best = float("inf")
for i in range(start + 1, len(debt)):
if debt[i] * debt[start] < 0:
debt[i] += debt[start]
best = min(best, 1 + dfs(start + 1))
debt[i] -= debt[start]
return best
return dfs(0)class Solution {
int dfs(vector<int>& debt, int start) {
while (start < (int) debt.size() && debt[start] == 0) start++;
if (start == (int) debt.size()) return 0;
int best = INT_MAX;
for (int i = start + 1; i < (int) debt.size(); i++) {
if ((long long) debt[i] * debt[start] < 0) {
debt[i] += debt[start];
best = min(best, 1 + dfs(debt, start + 1));
debt[i] -= debt[start];
}
}
return best;
}
public:
int minTransfers(vector<vector<int>>& transactions) {
vector<int> bal(12, 0);
for (auto& t : transactions) {
bal[t[0]] -= t[2];
bal[t[1]] += t[2];
}
vector<int> debt;
for (int b : bal) if (b != 0) debt.push_back(b);
return dfs(debt, 0);
}
};function minTransfers(transactions) {
const bal = new Array(12).fill(0);
for (const [f, t, amt] of transactions) {
bal[f] -= amt;
bal[t] += amt;
}
const debt = bal.filter((b) => b !== 0);
function dfs(start) {
while (start < debt.length && debt[start] === 0) start++;
if (start === debt.length) return 0;
let best = Infinity;
for (let i = start + 1; i < debt.length; i++) {
if (debt[i] * debt[start] < 0) {
debt[i] += debt[start];
best = Math.min(best, 1 + dfs(start + 1));
debt[i] -= debt[start];
}
}
return best;
}
return dfs(0);
}2Optimal (bitmask DP over zero-sum groups)
O(2^k · k)Each of the 2^k masks looks at up to k ways to drop one person; k is at most 12.O(2^k)Two arrays of size 2^k: subset sums and DP values.With k non-zero balances, settling a zero-sum group of size g takes g - 1 transfers, so the total is k minus the number of groups. Maximise the number of disjoint zero-sum groups with a DP over subsets: dp[mask] is the most groups that the people in mask can be split into, where only a mask with total 0 can be split completely. Removing any one person from the mask and adding 1 when the mask's sum is zero gives the recurrence.
- Compute balances and keep the k non-zero ones.
- Precompute
sum[mask]for every subset, building each frommaskwithout its lowest set bit. - For each mask in increasing order:
dp[mask] = max(dp[mask ^ (1 << i)])over set bitsi, then add 1 ifsum[mask] == 0. - Return
k - dp[(1 << k) - 1].
class Solution {
public int minTransfers(int[][] transactions) {
int[] bal = new int[12];
for (int[] t : transactions) {
bal[t[0]] -= t[2];
bal[t[1]] += t[2];
}
List<Integer> list = new ArrayList<>();
for (int b : bal) if (b != 0) list.add(b);
int k = list.size();
int full = 1 << k;
int[] sum = new int[full];
int[] dp = new int[full];
for (int mask = 1; mask < full; mask++) {
int low = Integer.numberOfTrailingZeros(mask);
sum[mask] = sum[mask & (mask - 1)] + list.get(low);
int best = 0;
for (int i = 0; i < k; i++) {
if ((mask >> i & 1) == 1) best = Math.max(best, dp[mask ^ (1 << i)]);
}
dp[mask] = best + (sum[mask] == 0 ? 1 : 0);
}
return k - dp[full - 1];
}
}class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
bal = [0] * 12
for f, t, amt in transactions:
bal[f] -= amt
bal[t] += amt
vals = [b for b in bal if b != 0]
k = len(vals)
full = 1 << k
total = [0] * full
dp = [0] * full
for mask in range(1, full):
low = (mask & -mask).bit_length() - 1
total[mask] = total[mask & (mask - 1)] + vals[low]
best = 0
for i in range(k):
if mask >> i & 1:
best = max(best, dp[mask ^ (1 << i)])
dp[mask] = best + (1 if total[mask] == 0 else 0)
return k - dp[full - 1]class Solution {
public:
int minTransfers(vector<vector<int>>& transactions) {
vector<int> bal(12, 0);
for (auto& t : transactions) {
bal[t[0]] -= t[2];
bal[t[1]] += t[2];
}
vector<int> vals;
for (int b : bal) if (b != 0) vals.push_back(b);
int k = vals.size();
int full = 1 << k;
vector<int> sum(full, 0), dp(full, 0);
for (int mask = 1; mask < full; mask++) {
int low = __builtin_ctz(mask);
sum[mask] = sum[mask & (mask - 1)] + vals[low];
int best = 0;
for (int i = 0; i < k; i++) {
if (mask >> i & 1) best = max(best, dp[mask ^ (1 << i)]);
}
dp[mask] = best + (sum[mask] == 0 ? 1 : 0);
}
return k - dp[full - 1];
}
};function minTransfers(transactions) {
const bal = new Array(12).fill(0);
for (const [f, t, amt] of transactions) {
bal[f] -= amt;
bal[t] += amt;
}
const vals = bal.filter((b) => b !== 0);
const k = vals.length;
const full = 1 << k;
const sum = new Array(full).fill(0);
const dp = new Array(full).fill(0);
for (let mask = 1; mask < full; mask++) {
const low = 31 - Math.clz32(mask & -mask);
sum[mask] = sum[mask & (mask - 1)] + vals[low];
let best = 0;
for (let i = 0; i < k; i++) {
if ((mask >> i) & 1) best = Math.max(best, dp[mask ^ (1 << i)]);
}
dp[mask] = best + (sum[mask] === 0 ? 1 : 0);
}
return k - dp[full - 1];
}Edge cases to test
- Everybody already even (for example A pays B and B pays A the same amount): the answer is 0
- A chain A -> B -> C of equal amounts: the middle person drops out and one transfer is enough
- Two independent pairs of debts: settle each pair separately
- Greedily matching the largest creditor with the largest debtor is not always optimal; groups whose balances sum to zero are what matters
Hints
Hint 1
Only the final balance of each person matters: add amount to to and subtract it from from. People with balance 0 can be ignored.
Hint 2
A group of k people whose balances add up to zero can always be settled with k - 1 transfers, and never with fewer if it cannot be split further.
Hint 3
So the answer is (number of non-zero balances) minus (the largest number of disjoint zero-sum groups they can be split into). Over at most 12 people, a DP over subsets finds that number: dp[mask] = max over i in mask of dp[mask without i], plus 1 when the balances in mask sum to zero.
FAQ
What is the best time complexity for Optimal Account Balancing?
Optimal (bitmask DP over zero-sum groups) runs in O(2^k · k) time and O(2^k) extra space. Each of the 2^k masks looks at up to k ways to drop one person; k is at most 12.
Which pattern does Optimal Account Balancing use?
It is a dynamic programming problem that uses the bitmask dp pattern. Other problems with the same pattern: Smallest Sufficient Team, Frequencies of Shortest Supersequences, Minimum Number of Work Sessions to Finish the Tasks.
Is there a brute force solution for Optimal Account Balancing?
Yes. Brute force (backtracking over who settles with whom) takes O(k!) time and O(k) space. Reduce the transactions to a list of non-zero balances.
Which edge cases should I test for Optimal Account Balancing?
Everybody already even (for example A pays B and B pays A the same amount): the answer is 0; A chain A - B - C of equal amounts: the middle person drops out and one transfer is enough; Two independent pairs of debts: settle each pair separately; Greedily matching the largest creditor with the largest debtor is not always optimal; groups whose balances sum to zero are what matters.