Optimal Account Balancing

Problem

You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.

Return the minimum number of transactions required to settle the debt.

Example 1:

Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Example 2:

Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

Constraints:

• 1 <= transactions.length <= 8
• transactions[i].length == 3
• 0 <= fromi, toi < 12
• fromi != toi
• 1 <= amounti <= 100

Solution

Backtracking

class Solution {
    public int minTransfers(int[][] transactions) {
        var balances = new int[12];

        for (var tx : transactions) {
            balances[tx[0]] -= tx[2];
            balances[tx[1]] += tx[2];
        }

        return backtrack(balances, 0, 0);
    }

    public int backtrack(int[] balances, int pos, int txs) {
        if (pos >= balances.length) {
            return txs;
        }

        // only try to balance negative accounts
        // the total money in the system is zero-sum so if we handle the negatives we know there will be no positives
        if (balances[pos] >= 0) {
            return backtrack(balances, pos + 1, txs);
        }

        var results = new ArrayList<Integer>();

        // see who can give us $$$
        for (var i = 0; i < balances.length; i++) {
            if (balances[i] > 0) {
                // try to take their money
                var copy = Arrays.copyOf(balances, balances.length);
                copy[pos] += copy[i];
                copy[i] = 0;
                results.add(backtrack(copy, pos, txs + 1));
            }
        }

        return results.stream().reduce(Math::min).orElse(-1);
    }
}

Greedy w/ Priority Queue

This is a greedy solution that doesn’t always return the ideal solution.

class Solution {
    public int minTransfers(int[][] transactions) {
        var moves = 0;
        var balance = new int[12];
        for (var t : transactions) {
            balance[t[0]] -= t[2];
            balance[t[1]] += t[2];
        }

        // stores indexes
        var debts = new PriorityQueue<Integer>((l, r) -> {
            return Integer.compare(balance[l], balance[r]);
        });
        var credits = new PriorityQueue<Integer>((l, r) -> {
            return Integer.compare(balance[r], balance[l]);
        });

        for (var i = 0; i < 12; i++) {
            // ignore anyone who is already balanced
            if (balance[i] > 0) {
                credits.offer(i);
            }
            if (balance[i] < 0) {
                debts.offer(i);
            }
        }

        while (!debts.isEmpty() && !credits.isEmpty()) {
            var richest = credits.poll();
            var poorest = debts.poll();

            var diff = balance[richest] + balance[poorest];
            if (diff >= 0) {
                // richest can pay off the entire debt
                balance[richest] += balance[poorest];
                balance[poorest] = 0;
                // re-add richest if they still have money
                if (balance[richest] > 0) {
                    credits.offer(richest);
                }
            } else {
                balance[poorest] += balance[richest];
                // don't re-add richest (they're balanced)
                // re-add poorest
                debts.offer(poorest);
            }

            moves += 1;
        }

        return moves;
    }
}

Greedy w/ Pairs

This is a version of the above that finds pairs which would cancel out accounts. It still doesn’t provide the optimal solution

class Solution {
    public int minTransfers(int[][] transactions) {
        var moves = 0;
        var balance = new int[12];
        for (var t : transactions) {
            balance[t[0]] -= t[2];
            balance[t[1]] += t[2];
        }

        // stores indexes
        var debts = new PriorityQueue<Integer>((l, r) -> {
            return Integer.compare(balance[l], balance[r]);
        });
        var credits = new PriorityQueue<Integer>((l, r) -> {
            return Integer.compare(balance[r], balance[l]);
        });

        for (var i = 0; i < 12; i++) {
            // ignore anyone who is already balanced
            if (balance[i] > 0) {
                credits.offer(i);
            }
            if (balance[i] < 0) {
                debts.offer(i);
            }
        }

        while (!debts.isEmpty() && !credits.isEmpty()) {
            var richest = credits.poll();
            var poorest = debts.poll();

            // check if there is anyone that would perfectly cancel out these accounts
            int poorestPartner = -1;
            for (var i = 0; i < balance.length; i++) {
                if (balance[i] * -1 == balance[poorest]) {
                    poorestPartner = i;
                    break;
                }
            }
            if (poorestPartner >= 0) {
                credits.offer(richest);
                credits.remove(poorestPartner);
                balance[poorest] = 0;
                balance[poorestPartner] = 0;
                moves += 1;
                continue;
            }

            int richestPartner = -1;
            for (var i = 0; i < balance.length; i++) {
                if (balance[i] * -1 == balance[richest]) {
                    richestPartner = i;
                    break;
                }
            }
            if (richestPartner >= 0) {
                debts.offer(poorest);
                debts.remove(richestPartner);
                balance[richest] = 0;
                balance[richestPartner] = 0;
                moves += 1;
                continue;
            }

            var diff = balance[richest] + balance[poorest];
            if (diff >= 0) {
                // richest can pay off the entire debt
                balance[richest] += balance[poorest];
                balance[poorest] = 0;
                // re-add richest if they still have money
                if (balance[richest] > 0) {
                    credits.offer(richest);
                }
            } else {
                balance[poorest] += balance[richest];
                balance[richest] = 0;
                // don't re-add richest (they're balanced)
                // re-add poorest
                debts.offer(poorest);
            }

            moves += 1;
        }

        System.out.println(debts);
        System.out.println(credits);

        return moves;
    }
}