Turning Final Balances Into the Fewest Possible Payments

The last post ended with getGroupBalances handing back one clean map: how much each person in the group actually owes or is owed, once every unsettled expense gets added up.

That map does not say who should pay who. This post turns it into an actual list of payments.

Turn the Balances Into Two Piles

Picture a group of seven people once every expense has been summed into a final balance per person.

Positive means the group owes them money. Negative means they owe the group money. Split the group into two piles based on that sign.

The positive pile: everyone who is owed money, largest amount first. The negative pile: everyone who owes money, largest amount first.

The whole settlement problem is just: connect people in the positive pile with people in the negative pile until every balance hits zero. Each connection is one payment, one edge in the graph.

The Greedy Algorithm, Step by Step

Here's the idea in one sentence: on every round, take the person owed the most and the person who owes the most, settle the smaller of their two amounts as a single payment, and push whichever one still has money left back into their pile.

The data structure that makes "always grab the largest" cheap is a heap. You build two of them: a max-heap of positive balances and a max-heap of negative balances, ordered by size, not by sign.

Each round works the same way.

1. Pop the top of the positive heap and the top of the negative heap.
2. Whichever amount is smaller becomes one payment: the negative person pays that amount to the positive person.
3. Subtract that amount from both balances.
4. Whichever side still has a nonzero balance left gets pushed back into its heap. The side that hit exactly zero is done and drops out of the graph for good.

Every single round removes at least one person from the graph entirely. That is what keeps the algorithm fast and keeps it terminating: the piles only ever shrink.

In Java, the data structure that actually implements a heap under the hood is PriorityQueue. The real reference implementation for this project uses exactly two of them, one for positive balances and one for negative, so this same mechanic is what you will see written as real code in a later, hands-on post.

This Is a Heuristic, Not the Optimal Answer

Say this plainly, because it is easy to assume "the largest-first approach" must be the smartest one: the greedy algorithm above does not always find the true minimum number of payments.

Here is a set of balances where it visibly falls short.

Seven people, final balances: A is owed $80, B is owed $25, C owes $25, and D, E, F, and G each owe $20.

Run the greedy algorithm on that.

It takes six payments to settle everyone, when five is actually enough.

ExpandTwo ways to settle the same seven balances, greedy taking six payments and the best possible taking five

Walk through why. Greedy always grabs the two largest amounts first, so it starts by matching C's $25 debt against A's $80 credit, not against B's $25 credit, even though C and B match each other perfectly.

That one wrong pairing at the start is what costs the sixth payment. A version that noticed C's $25 debt exactly cancels B's $25 credit could settle that pair in one move and then let D, E, F, and G each pay A directly. Same final balances, five payments instead of six.

Why a Smarter-Looking Fix Still Doesn't Fully Work

The obvious patch is: before running greedy, first scan both piles for any exact-equal pairs and cancel those out directly, then fall back to greedy for whatever is left.

That patch does catch the C-and-B case above. It still is not guaranteed to find the true minimum in every case, though.

The reason is that "exact pairs" is just one narrow kind of lucky match. A group's balances can need money routed through two, three, or more people at once to reach the fewest possible payments, in combinations no simple pre-scan rule will reliably spot. Special-casing the obvious wins narrows the gap. It does not close it.

Why Greedy Is Still the Right Interview Answer

Finding the true minimum number of transactions for an arbitrary set of balances is closely related to the subset-sum problem: given a set of numbers, is there some combination of them that adds up to a specific target. That problem does not have a fast, known way to solve it exactly, since every added person roughly doubles the combinations worth checking.

Reaching for that level of exactness in a machine coding round does not make practical sense. Greedy is simple to explain, simple to code, and fast, since a heap operation is cheap even as the group grows. That combination is exactly what a 60-to-90-minute round is testing.

If the exact-optimal version genuinely interests you, the subset-sum problem is the concept to go read up on separately. It is not what this post is solving, and it is not what an interviewer expects you to solve live either.

The BookMyShow requirements post covers the same instinct from a different angle: know which parts of a hard problem are actually worth solving exactly in an interview, and which ones are worth naming out loud and moving past.

Before any code gets written, two more design decisions are worth making: which APIs in this tracker are worth caching, and what happens to that cache under concurrent reads and writes. The next post covers both.