LeetCode 465: Optimal Account Balancing

Problem Restatement

We are given a list of transactions.

Each transaction has the form:

[from_person, to_person, amount]

This means from_person gave amount dollars to to_person.

After all original transactions, some people may owe money and some people may be owed money.

We need to return the minimum number of transactions required to settle all debts. The official problem defines each transaction as [from_i, to_i, amount_i] and asks for the minimum number of transactions needed to settle the debt.

Input and Output

Function shape:

def minTransfers(transactions: list[list[int]]) -> int:
    ...

Examples

Example 1:

transactions = [[0, 1, 10], [2, 0, 5]]

Interpretation:

0 gave 1 ten dollars
2 gave 0 five dollars

Net balances:

One optimal settlement is:

0 pays 1 five dollars
2 pays 1 five dollars

Answer:

2

Example 2:

transactions = [[0, 1, 10], [1, 0, 1], [1, 2, 5], [2, 0, 5]]

Net balances:

Only one transaction is needed:

0 pays 1 four dollars

Answer:

1

First Thought: Settle Debtors With Creditors Greedily

A natural idea is:

1. Compute who owes money.
2. Compute who should receive money.
3. Match a debtor with a creditor.
4. Transfer as much as possible.
5. Repeat until all balances are zero.

This always produces a valid settlement.

For example, if:

balances = [-7, 5, 2]

then the person with -7 can pay 5 to one creditor and 2 to another creditor.

That uses two transactions.

The problem is that greedy matching does not always minimize the transaction count. We need to search over possible pairings.

Problem With Greedy

The minimum number of transactions depends on how balances can cancel in groups.

For example, if a subset of people has balances that sum to zero, that subset can be settled internally.

Good grouping can reduce the number of transactions.

A greedy choice may settle one person quickly but prevent a better zero-sum grouping later.

So the safe solution is backtracking over non-zero balances.

Key Insight

The original transaction graph does not matter after we compute net balances.

For each person:

balance = total_received - total_paid

Then:

The problem becomes:

Given a list of non-zero balances whose sum is 0, what is the fewest pairwise transfers needed to make all balances zero?

We can solve this with DFS.

At each step, take the first unsettled person and try to settle them with an opposite-sign person.

Balance Computation

For a transaction:

from_person gives amount to to_person

we update:

balance[from_person] -= amount
balance[to_person] += amount

This convention means:

After all transactions, only non-zero balances matter.

Algorithm

Compute net balances.

Build an array:

debts

containing only non-zero balances.

Then run:

dfs(start)

where start is the first index we still need to settle.

Inside dfs(start):

1. Skip all zero balances.
2. If start reaches the end, return 0.
3. Try pairing debts[start] with each later balance of opposite sign.
4. Temporarily add debts[start] into that later balance.
5. Recurse on start + 1.
6. Undo the change.
7. Take the minimum over all choices.

Why the update works:

debts[i] += debts[start]

means we use one transaction to settle debts[start] completely against debts[i].

Then index start can be treated as settled.

Walkthrough

Use:

transactions = [[0, 1, 10], [2, 0, 5]]

Net balances:

person 0: -5
person 1: 10
person 2: -5

So:

debts = [-5, 10, -5]

Start at index 0.

debts[0] = -5, so we need an opposite sign value.

The only positive value is debts[1] = 10.

Settle index 0 with index 1:

debts[1] += debts[0]
debts[1] = 10 + (-5) = 5

Now the remaining problem is:

[0, 5, -5]

Then settle 5 with -5.

That takes one more transaction.

Total:

2

Correctness

After computing net balances, any valid settlement only needs to make every net balance zero. The original path of transactions no longer affects the answer.

The DFS always chooses the first unsettled balance.

That balance must be settled by sending money to or receiving money from some later balance with the opposite sign. Pairing with the same sign cannot reduce both balances toward zero.

For every possible opposite-sign partner, the algorithm tries one transaction that fully settles the current balance and transfers the remaining imbalance to the partner.

This covers every possible optimal settlement, because in any valid settlement the current unsettled person must participate in at least one transaction with an opposite-sign person.

The recursion then solves the remaining unsettled balances optimally.

Since the algorithm takes the minimum over all possible partners, it returns the minimum number of transactions.

Complexity

Let m be the number of people with non-zero balances.

The input constraints are small enough for this backtracking approach.

Implementation

from collections import defaultdict

class Solution:
    def minTransfers(self, transactions: list[list[int]]) -> int:
        balance = defaultdict(int)

        for from_person, to_person, amount in transactions:
            balance[from_person] -= amount
            balance[to_person] += amount

        debts = [value for value in balance.values() if value != 0]

        def dfs(start: int) -> int:
            while start < len(debts) and debts[start] == 0:
                start += 1

            if start == len(debts):
                return 0

            best = float("inf")

            for i in range(start + 1, len(debts)):
                if debts[start] * debts[i] >= 0:
                    continue

                debts[i] += debts[start]
                best = min(best, 1 + dfs(start + 1))
                debts[i] -= debts[start]

            return best

        return dfs(0)

Code Explanation

We first compute net balances:

balance[from_person] -= amount
balance[to_person] += amount

Then we remove people who are already settled:

debts = [value for value in balance.values() if value != 0]

The DFS skips zero balances:

while start < len(debts) and debts[start] == 0:
    start += 1

If every balance is zero, no more transactions are needed:

if start == len(debts):
    return 0

Then we try to settle debts[start] with each later opposite-sign balance:

if debts[start] * debts[i] >= 0:
    continue

The temporary settlement is:

debts[i] += debts[start]

This uses one transaction to eliminate debts[start].

Then we recurse:

best = min(best, 1 + dfs(start + 1))

After recursion, we undo the change:

debts[i] -= debts[start]

Finally, return the best result.

Pruned Implementation

We can add two simple pruning rules.

First, if a pairing makes the partner exactly zero, that is often the best local cancellation, so we can stop trying other partners at this level.

Second, we can skip duplicate partner balances to avoid repeated equivalent work.

from collections import defaultdict

class Solution:
    def minTransfers(self, transactions: list[list[int]]) -> int:
        balance = defaultdict(int)

        for from_person, to_person, amount in transactions:
            balance[from_person] -= amount
            balance[to_person] += amount

        debts = [value for value in balance.values() if value != 0]

        def dfs(start: int) -> int:
            while start < len(debts) and debts[start] == 0:
                start += 1

            if start == len(debts):
                return 0

            best = float("inf")
            seen = set()

            for i in range(start + 1, len(debts)):
                if debts[i] in seen:
                    continue

                if debts[start] * debts[i] >= 0:
                    continue

                seen.add(debts[i])

                debts[i] += debts[start]
                best = min(best, 1 + dfs(start + 1))
                debts[i] -= debts[start]

                if debts[i] + debts[start] == 0:
                    break

            return best

        return dfs(0)

The first implementation is simpler. The pruned version is better for harder cases.

Testing

def run_tests():
    s = Solution()

    assert s.minTransfers([[0, 1, 10], [2, 0, 5]]) == 2

    assert s.minTransfers([
        [0, 1, 10],
        [1, 0, 1],
        [1, 2, 5],
        [2, 0, 5],
    ]) == 1

    assert s.minTransfers([]) == 0

    assert s.minTransfers([[0, 1, 5], [1, 0, 5]]) == 0

    assert s.minTransfers([
        [0, 1, 10],
        [1, 2, 10],
    ]) == 1

    assert s.minTransfers([
        [0, 1, 10],
        [2, 3, 10],
    ]) == 2

    print("all tests passed")

run_tests()

Test meaning: