Coding · Backtracking
Settle group expenses with the fewest payments
- Reported once
- Hard
- Software Engineer (campus)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A group has recorded who handed money to whom: each record [from, to, amount] says that person from handed a positive whole amount to person to, so the receiver owes it back. Find the smallest number of payments that settles everyone, where a payment may move any amount between any two people. For example, the records [[0,1,10],[2,0,5]] mean person 1 owes 10 to person 0 and person 0 owes 5 to person 2, so the best settlement takes 2 payments: person 1 pays 5 to person 0 and 5 to person 2. A candidate report lists it as a face-to-face design question, minimising the give and take in an app like Splitwise, where each user adds what they spend and it is shared equally. This version takes the debts as who-owes-whom records, the usual form of the problem. Assume at most about a dozen people end up with a non-zero balance.
Restated in our own words, not a quote from CRED or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask what a record means and what a payment may look like. Is [from, to, amount] a loan from the first person to the second? Are amounts whole numbers, such as paise, so that balances cancel exactly? May a settling payment go between any two people, or only between people who already have a record? Is the output the count of payments or the payments themselves? And how many people are involved, since the search I have in mind is exponential?
My assumptions: each record means from handed amount to to, amounts are positive integers, any person may pay any other, I return the minimum count, and at most about a dozen people have a non-zero balance. The report describes bills shared equally in a Splitwise-like app; I would first turn each bill into records, one per non-paying member who owes the payer a share, and then solve the records form. Listing the payments is a small extension.
Brute force
Say the obvious answer and why it is too slow.
The first idea is to settle the records as they are, one repayment per record in the opposite direction. That is correct but wasteful, because records between the same people cancel and chains collapse. A person who lent 10 and borrowed 10 should not appear at all.
The honest brute force first reduces to net balances and then tries every order of settling: pick an unsettled person, try every person of the opposite sign as the counterparty, move the balance, and recurse. With n non-zero balances that is on the order of (n-1)! paths, and it keeps re-exploring states that differ only in which equal-valued person was chosen. A tempting shortcut, always matching the largest debtor with the largest creditor, is fast but not optimal, as the slips section shows.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n!) orderings of payments with no pruning
- Time
- O((n-1)!) worst case for n non-zero balances, far less after pruning
- Space
- O(n) for the balances and the recursion
The pattern is backtracking on net balances, after one reduction that does most of the thinking. Only each person's net position matters: add the amount received and subtract the amount given. Drop everyone at zero. A positive balance means the person owes the group, a negative one means the group owes them, and all balances sum to zero.
Now count payments cleverly. Any valid set of payments connects the people with non-zero balances into groups, and a connected group of g people needs at least g-1 payments. Each group must sum to zero, since money only moves inside it, and bringing a person with a zero balance into a group only adds payments. So the number of payments is at least n minus the number of groups, and a zero-sum group of g people can always be settled in exactly g-1 payments by clearing one person at a time. The problem is therefore: split the balances into as many zero-sum groups as possible.
The search does that implicitly. Take the first unsettled person and try every person with the opposite sign: one payment moves the first person's whole balance onto that counterparty, which clears the first person and leaves the counterparty with the sum. Recurse on the rest and keep the minimum. Two pruning rules keep it small. If two candidates have the same balance, trying the second repeats the first, so skip it. If a candidate exactly cancels the first person, take it and stop: pairing them as a group of their own never reduces the number of zero-sum groups. The balances are changed before each recursive call and restored after it.
Out loud: "net the balances, then minimise payments by backtracking over who absorbs the first person's balance, with the duplicate and exact-cancel pruning rules. The worst case is exponential, which is fine for a dozen people."
Walk it through
A dry run on the example, step by step.
| Step | Settles | With | Left to settle | Payments |
|---|---|---|---|---|
| 1 | -5 | 3 | -2, -3, 3, 2 | 1 |
| 2 | -2 | 3 | -3, 1, 2 | 2 |
| 3 | -3 | 1 | -2, 2 | 3 |
| 4 | -2 | 2 | all zero | 4 |
| 5 | -3 | 2 | 1, -1 | 3 |
| 6 | 1 | -1 | all zero | 4 |
| 7 | -2 | 2 | -3, 3, 0 | 2 |
| 8 | -3 | 3 | all zero | 3 |
| 9 | -5 | 2 | 3, -3, 3, -3 | 1 |
| 10 | 3 | -3 | 0, 3, -3 | 2 |
| 11 | 3 | -3 | all zero | 3 |
Take the records [[0,2,3],[1,3,3],[0,4,2]]. Person 0 handed out 5 in total, so the balance is -5. Person 2 received 3, person 1 handed out 3, person 3 received 3 and person 4 received 2. In order of first appearance the balances are -5, 3, -3, 3 and 2, which sum to zero.
Step 1 merges the -5 into the first 3, which becomes -2; the same merge with the second 3 is skipped because it would repeat the work. Step 2 pairs the -2 with the next 3, leaving 1, step 3 pairs the -3 with that 1, leaving -2, and step 4 pairs the -2 with the 2, so everything is zero after 4 payments. Step 5 backtracks and tries the -3 against the 2, and step 6 finishes again with 4 payments. Step 7 instead pairs the -2 with the 2, an exact cancellation, leaving -3 and 3, and step 8 cancels those: 3 payments. Steps 9 to 11 try the -5 against the 2 and reach 3 again. The minimum is 3, from the groups {-5, 3, 2} and {-3, 3}.
The code
Runnable JavaScript, checked against test cases.
function minTransfers(transactions) {
const net = new Map();
for (const [from, to, amount] of transactions) {
net.set(from, (net.get(from) ?? 0) - amount);
net.set(to, (net.get(to) ?? 0) + amount);
}
const debts = [...net.values()].filter((value) => value !== 0);
function settle(start) {
while (start < debts.length && debts[start] === 0) start++;
if (start === debts.length) return 0;
let best = Infinity;
const tried = new Set();
for (let j = start + 1; j < debts.length; j++) {
if (debts[j] * debts[start] >= 0 || tried.has(debts[j])) continue;
tried.add(debts[j]);
debts[j] += debts[start];
best = Math.min(best, 1 + settle(start + 1));
debts[j] -= debts[start];
if (debts[j] + debts[start] === 0) break;
}
return best;
}
return settle(0);
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No records, or records that cancel out exactly, leave no non-zero balance and the answer is 0 without entering the search. A record from a person to themselves changes nothing. Two people with opposite balances need one payment, and k people who all owe one person need k payments, because no subset of them sums to zero.
- One big group: n non-zero balances with no zero-sum subset need n-1 payments.
- Independent groups: they are found by the exact-cancel and search steps and their costs add up.
- Repeated equal balances: the tried-set skips equal partners, which matters for speed and not for correctness.
- Fractions: floating point amounts would make exact cancellation fail, so keep integer amounts such as paise.
- Person ids: any value usable as a map key works, numbers or names.
Follow-ups to expect
Where the interviewer pushes next.
- Can you beat factorial time, for example with a bitmask over subsets of people?
- How would you output the actual payments, meaning who pays whom and how much?
- Why is the exact-cancel shortcut safe, and can you prove it?
- How would you handle cents and rounding when a bill is split three ways?
- Is the problem hard in general, and what would you do for a group of fifty people?
Where candidates slip
The mistakes this problem punishes.
The classic wrong answer is the greedy that always settles the largest debtor with the largest creditor. With balances 5, 4, 1, -4, -3 and -3 it can take 5 payments, while pairing 4 with -4 and settling the other four people together takes 4. Greedy gives at most n-1 payments but not the minimum.
Other slips: settling per record instead of per net balance; forgetting to undo the change after the recursive call, so later branches see corrupted balances; not skipping people already at zero, which counts payments that do not exist; breaking out of the loop after a match that is not exact; and using floating point amounts, where balances that should cancel differ by a rounding error.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.