Minimize Cash Flow among a given set of friends who have borrowed money from each other

The problem, simply

There are n friends and a list of IOUs. Each IOU says "friend a owes friend b some amount". Some friends owe and are owed at the same time, so paying every IOU moves a lot of money back and forth.

Find a set of payments that leaves everyone even and moves the least total money. Print who pays whom and how much.

A story to remember it

Picture it

Examples

Way 1: the simple way

First turn the tangle into one balance per friend. Then, each round, scan everyone to find the friend owed the most and the friend who owes the most. The one who owes pays the smaller of the two amounts, so at least one of them becomes even.

1. For each IOU a owes b x: net[a] -= x and net[b] += x.
2. Scan for max (largest balance) and min (most negative balance).
3. If net[max] is 0, everyone is even. Stop.
4. Pay amount = min(net[max], -net[min]) from min to max, update both, and go back to step 2.

import java.util.*;

class Solution {
    // each debt is {from, to, amount}; each payment is {payer, receiver, amount}
    public List<int[]> settle(int n, int[][] debts) {
        int[] net = new int[n];
        for (int[] d : debts) {
            net[d[0]] -= d[2];               // the one who owes goes down
            net[d[1]] += d[2];               // the one who is owed goes up
        }
        List<int[]> payments = new ArrayList<>();
        while (true) {
            int max = 0, min = 0;
            for (int i = 1; i < n; i++) {
                if (net[i] > net[max]) max = i;
                if (net[i] < net[min]) min = i;
            }
            if (net[max] == 0) break;        // everyone is even
            int amount = Math.min(net[max], -net[min]);
            payments.add(new int[]{min, max, amount});
            net[max] -= amount;
            net[min] += amount;
        }
        return payments;
    }
}

How long it takes: building the balances is O(m) for m IOUs. Every payment makes at least one friend even, so there are at most n - 1 rounds, and each round scans n friends. That is O(m + n^2). Extra room: the balances, O(n).

Way 2: the clever way

The scans are the slow part. Keep the friends who are owed money in one max-heap and the friends who owe money in another, both ordered by amount. A heap is a pile that always hands you its biggest item quickly.

1. Build the balances as before.
2. Put every positive balance in the getters heap and every negative balance, as a positive number, in the givers heap. Friends at 0 are already done.
3. While getters is not empty: take the top of each heap. The giver pays amount = min of the two. Whoever still has money left goes back into their heap.

import java.util.*;

class Solution {
    public List<int[]> settle(int n, int[][] debts) {
        int[] net = new int[n];
        for (int[] d : debts) {
            net[d[0]] -= d[2];
            net[d[1]] += d[2];
        }
        // entries are {amount, friend}: biggest amount first, then the smaller friend number
        Comparator<int[]> biggest = (x, y) -> x[0] != y[0] ? Integer.compare(y[0], x[0]) : Integer.compare(x[1], y[1]);
        PriorityQueue<int[]> getters = new PriorityQueue<>(biggest);
        PriorityQueue<int[]> givers = new PriorityQueue<>(biggest);
        for (int i = 0; i < n; i++) {
            if (net[i] > 0) getters.add(new int[]{net[i], i});
            else if (net[i] < 0) givers.add(new int[]{-net[i], i});
        }
        List<int[]> payments = new ArrayList<>();
        while (!getters.isEmpty()) {
            int[] g = getters.poll();
            int[] d = givers.poll();
            int amount = Math.min(g[0], d[0]);
            payments.add(new int[]{d[1], g[1], amount});            // d pays g
            if (g[0] > amount) getters.add(new int[]{g[0] - amount, g[1]});
            if (d[0] > amount) givers.add(new int[]{d[0] - amount, d[1]});
        }
        return payments;
    }
}

How long it takes: O(m) for the balances, then at most n - 1 payments, each with a few heap steps of O(log n). Total O(m + n log n). Extra room: the balances and the heaps, O(n).

Another way: the fewest payments

The greedy always moves the least money: exactly the sum of the positive balances, which no plan can beat. It also never needs more than n - 1 payments. But it does not always use the fewest payments.

Take balances -3, -2, -2, +3, +4. The greedy pairs +4 with -3 first and needs 4 payments. Better: the -3 pays the +3, and the two -2 friends pay the +4. That is 3 payments. Finding the fewest payments in general means splitting the friends into as many groups as possible where each group adds up to 0, which is a hard search problem. For small n you can try every way:

class Solution {
    public int fewestPayments(int n, int[][] debts) {
        int[] net = new int[n];
        for (int[] d : debts) {
            net[d[0]] -= d[2];
            net[d[1]] += d[2];
        }
        return search(net, 0);
    }

    // settle friend i with some later friend of the other sign, then move on
    private int search(int[] net, int i) {
        while (i < net.length && net[i] == 0) i++;
        if (i == net.length) return 0;
        int best = Integer.MAX_VALUE;
        for (int j = i + 1; j < net.length; j++) {
            if ((net[i] > 0) != (net[j] > 0) && net[j] != 0) {
                net[j] += net[i];                         // i hands their whole balance to j
                best = Math.min(best, 1 + search(net, i + 1));
                net[j] -= net[i];                         // undo
            }
        }
        return best;
    }
}

This tries up to O(n!) orders, so it is only for about a dozen friends. It is the LeetCode problem "Optimal Account Balancing".

Watch out for

• Build balances first. Settling IOU by IOU keeps the circles of debt.
• Friends with balance 0 must not enter a heap, or you will make payments of 0.
• The balances always add up to 0, so when the getters heap is empty the givers heap is empty too.
• Large sums can overflow int. Use long if amounts are big.
• If the input is an n by n table instead of a list, building balances costs O(n^2), and that dominates.

What interviewers ask next

• Why is the money moved minimal? Every getter must receive at least their balance, so any plan moves at least the sum of positive balances, and the greedy moves exactly that.
• Why at most n - 1 payments? Each payment makes at least one friend even, and the last two friends become even together.
• How would you build this for a real app like a shared expense tracker? Keep running balances per friend as expenses come in, and only run the settle step when someone asks to settle up.
• Can you do it without heaps in O(n log n)? Sort the givers and getters by amount and walk two pointers from the big ends. You get a valid plan with at most n - 1 payments, just not always the same pairing.

Remember this

Grown-up words: the friends and IOU arrows are a directed weighted graph, the balance is the net flow of each node, the two piles are max-heaps (priority queues), and splitting into zero-sum groups is an NP-hard partition problem.