Minimize Cash Flow Among Friends

Minimize Cash Flow Among Friends is a classic greedy problem. A group of friends lend each other money over a trip, and you want to settle up using the fewest possible payments. The trick is to stop thinking about individual loans and start thinking about each person's net balance.

The slow way first

You could try every possible set of payments and keep the smallest — but the number of ways to settle a graph of debts is astronomical, and finding the true minimum is actually an NP-hard partition problem. We do not need perfection, though. A simple greedy rule produces a settlement that is minimal in practice and easy to reason about.

The question to ask: do the original loans even matter? If A owes B and B owes C, the chain can collapse. All that matters at the end is how much each person is up or down overall.

The idea: net out, then settle extremes

First compute each friend's net balance: add what they received, subtract what they paid. Positive means they are owed money (a creditor); negative means they owe money (a debtor). The balances always sum to zero.

Then repeat: take the friend who is owed the most and the friend who owes the most, and have the debtor pay the creditor the smaller of the two amounts. That single payment drives at least one of them to exactly zero, removing them from the problem.

Why settle the extremes? Paying the smaller amount guarantees at least one person is fully settled every round, so each transaction permanently shrinks the problem. With n people that is at most n − 1 transfers.

Walk through it

Step through the animation. Balances start at A = −5, B = +3, C = +2. The biggest creditor is B and the biggest debtor is A, so A pays B min(5, 3) = 3; B hits 0 and leaves. Now A = −2 and C = +2, so A pays C min(2, 2) = 2; both reach 0. Two transactions and everyone is square.

Pseudocode

bal = array of zeros, one per friend
for each (from, to, amount) in transactions:
    bal[from] -= amount          # the payer is down
    bal[to]   += amount          # the receiver is up
count = 0
while some balance is non-zero:
    cr = index of the largest balance     # biggest creditor
    db = index of the smallest balance    # biggest debtor
    give = min(-bal[db], bal[cr])         # the smaller amount
    bal[db] += give                       # debtor pays it off
    bal[cr] -= give                       # creditor receives it
    count += 1                            # one transfer
return count

The Python solution

def min_cash_flow(n, transactions):
    bal = [0] * n
    for frm, to, amt in transactions:
        bal[frm] -= amt
        bal[to] += amt
    count = 0
    while any(b != 0 for b in bal):
        cr = bal.index(max(bal))
        db = bal.index(min(bal))
        give = min(-bal[db], bal[cr])
        bal[db] += give
        bal[cr] -= give
        count += 1
    return count

• bal holds each friend's net position; the first loop converts raw loans into balances.
• A payer loses money (-= amt) and a receiver gains it (+= amt), so the array always sums to zero.
• bal.index(max(bal)) finds the biggest creditor; bal.index(min(bal)) finds the biggest debtor.
• give = min(-bal[db], bal[cr]) is the largest transfer that does not overshoot either person.
• Applying give zeroes at least one of them, so the while loop runs at most n − 1 times.

Complexity

The balance array is the whole trick: it throws away the original loan structure and leaves only what matters. Settling the extremes greedily then keeps the transfer count small.

When this pattern shows up

Practice