Optimal Account Balancing
On this page
Problem statement
A group of friends recorded who lent money to whom. Each record is
[lender, borrower, amount]. Return the minimum number of payments needed so that everyone ends up even. Any person may pay any other person any amount.
This is the "split the bill" problem behind expense-sharing apps, and a favourite at payments and fintech companies. It looks like a graph problem, but the key step is throwing the graph away: only each person's net balance matters. Original problem: LeetCode 465.
Example

Input: [[Alice, Bob, 6], [Bob, Carol, 10], [Carol, Dan, 6]] # as ids: [[0,1,6],[1,2,10],[2,3,6]]
Net: Alice +6, Bob +4, Carol -4, Dan -6
Output: 2 # Dan pays Alice 6, Carol pays Bob 4
Input: [[0,1,5], [1,0,5]]
Output: 0 # the two loans cancel out
Constraints (assumed)
- 1 ≤ number of records ≤ 8; person ids are small integers; amounts are positive.
- After netting, at most about 12 people have a non-zero balance. That small limit is a hint that exponential search is expected.
What this question tests
- Reducing the input to net balances and ignoring who originally lent to whom.
- Seeing that greedy settling is not optimal, and that the real goal is to find many disjoint groups that sum to zero.
- Writing a backtracking search with pruning that is fast enough, or the equivalent bitmask DP.
Questions to ask first
- Can anyone pay anyone, even people who never traded directly? (Here: yes.)
- Do we count payments or total money moved? (Here: the number of payments. Total money moved is always the same: the sum of the positive balances.)
- How many people can there be? The answer decides between exponential search and "good enough" greedy.
- Are amounts integers? (Here: yes. With money, use cents to avoid float errors.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.