Optimal Account Balancing

Hard Dynamic Programming Bitmask DP Original on LeetCode

Reported atStripePinterest

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 <= 8
  • transactions[i] = [from, to, amount]
  • 0 <= from, to < 12 and from != to
  • 1 <= 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(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.
SpaceO(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.

  1. Compute the balance of every person and keep only the non-zero ones in a list debt.
  2. dfs(start): skip indices with debt[start] == 0; if start reaches the end, return 0.
  3. For each i > start with debt[i] * debt[start] < 0: add debt[start] to debt[i], take 1 + dfs(start + 1), then undo.
  4. 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;
    }
}

2Optimal (bitmask DP over zero-sum groups)

TimeO(2^k · k)Each of the 2^k masks looks at up to k ways to drop one person; k is at most 12.
SpaceO(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.

  1. Compute balances and keep the k non-zero ones.
  2. Precompute sum[mask] for every subset, building each from mask without its lowest set bit.
  3. For each mask in increasing order: dp[mask] = max(dp[mask ^ (1 << i)]) over set bits i, then add 1 if sum[mask] == 0.
  4. 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];
    }
}

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.