Minimise the cashflow among a given set of friends who have borrowed money from each other

The problem, simply

N friends lent each other money. You get a table: owes[i][j] is how much friend i owes friend j.

Find a list of payments that makes everyone even, so that the total money moved is as small as possible. The classic solution also uses at most N - 1 payments. Print or return the payments.

A story to remember it

Picture it

Examples

Way 1: the simple way

Pay every debt as written, but first cancel debts that go both ways: if i owes j 30 and j owes i 10, then i pays j 20 and that is it.

1. For every pair i < j, compute d = owes[i][j] - owes[j][i].
2. If d > 0, i pays j the amount d. If d < 0, j pays i the amount -d.

import java.util.*;

class Solution {
    // each payment is {from, to, amount}
    public List<int[]> settle(int[][] owes) {
        int n = owes.length;
        List<int[]> pays = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int d = owes[i][j] - owes[j][i];        // cancel back and forth
                if (d > 0) pays.add(new int[]{i, j, d});
                else if (d < 0) pays.add(new int[]{j, i, -d});
            }
        }
        return pays;
    }
}

How long it takes: one look at every pair, O(N^2). Extra room besides the answer: O(1). But it can need up to N * (N - 1) / 2 payments, and money goes round in circles: in the circle example, it makes three payments when none are needed.

Way 2: the clever way

Only the net amount of each friend matters. Who owed whom along the way does not.

1. For each friend, net[i] = everything others owe i minus everything i owes others. The nets always add up to 0.
2. Find the biggest receiver cr (largest net) and the biggest payer dr (smallest net).
3. If net[cr] is 0, everyone is even: stop.
4. dr pays cr the amount min(net[cr], -net[dr]). Update both nets and repeat.

Each payment makes at least one of the two friends exactly even, and an even friend never pays or receives again. So there are at most N - 1 payments. The money moved is the sum of all positive nets, which is the least possible: every receiver must get at least their net.

import java.util.*;

class Solution {
    // each payment is {from, to, amount}
    public List<int[]> minCashFlow(int[][] owes) {
        int n = owes.length;
        int[] net = new int[n];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                net[i] += owes[j][i] - owes[i][j];       // what i gets minus what i pays

        List<int[]> pays = new ArrayList<>();
        while (true) {
            int cr = 0, dr = 0;
            for (int i = 1; i < n; i++) {
                if (net[i] > net[cr]) cr = i;            // biggest receiver
                if (net[i] < net[dr]) dr = i;            // biggest payer
            }
            if (net[cr] == 0) break;                     // everyone is even
            int amount = Math.min(net[cr], -net[dr]);
            net[cr] -= amount;
            net[dr] += amount;
            pays.add(new int[]{dr, cr, amount});
        }
        return pays;
    }
}

How long it takes: building the nets reads the whole table, O(N^2). Then at most N - 1 payments, each finding the max and min in O(N), which is also O(N^2). Extra room: the net array, O(N).

Watch out for

• Getting the sign backwards. Pick one rule and stick to it: net[i] is what i should receive minus what i should pay.
• Using net[cr] == 0 as the stop test only works because the nets sum to 0: if the biggest receiver is even, nobody is owed anything, so nobody owes anything either.
• Large amounts. If debts can reach billions, use long for the nets.
• The recursive version from GeeksforGeeks is the same idea. A loop avoids a deep call stack.

What interviewers ask next

• Can you make the matching faster? Put receivers in a max-heap and payers in a max-heap of debts. Each payment then costs O(log N), so settling is O(N log N) after the nets are built.
• Why is the moved money minimal? Each receiver must get at least their net, so the total moved is at least the sum of positive nets, and greedy moves exactly that.
• Fewest number of payments? Split the friends into as many groups as possible where each group's nets sum to 0. A group of k people needs k - 1 payments, so the answer is N - (number of groups). With up to about 12 people, a bitmask search finds it.
• How would Splitwise do it? Exactly this: compute nets per person, then match payers and receivers greedily, often with heaps.

Remember this

Grown-up words: friends are vertices, debts are directed weighted edges, the net is the balance (incoming minus outgoing weight), plus friends are creditors, minus friends are debtors, and always settling the extremes is a greedy algorithm.