# LeetCode 465: Optimal Account Balancing

## Problem Restatement

We are given a list of transactions.

Each transaction has the form:

```python
[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

| Item | Meaning |
|---|---|
| Input | `transactions`, a list of money transfers |
| Transaction | `[from_person, to_person, amount]` |
| Output | Minimum number of new transactions needed |
| Goal | Make every person's net balance become `0` |

Function shape:

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

## Examples

Example 1:

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

Interpretation:

```python
0 gave 1 ten dollars
2 gave 0 five dollars
```

Net balances:

| Person | Net balance | Meaning |
|---:|---:|---|
| 0 | -5 | Owes 5 |
| 1 | 10 | Should receive 10 |
| 2 | -5 | Owes 5 |

One optimal settlement is:

```python
0 pays 1 five dollars
2 pays 1 five dollars
```

Answer:

```python
2
```

Example 2:

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

Net balances:

| Person | Net balance |
|---:|---:|
| 0 | -4 |
| 1 | 4 |
| 2 | 0 |

Only one transaction is needed:

```python
0 pays 1 four dollars
```

Answer:

```python
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:

```python
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:

```python
balance = total_received - total_paid
```

Then:

| Balance | Meaning |
|---:|---|
| Positive | This person should receive money |
| Negative | This person owes money |
| Zero | Already settled |

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:

```python
from_person gives amount to to_person
```

we update:

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

This convention means:

| Update | Meaning |
|---|---|
| `-amount` | The giver is owed less, or owes more |
| `+amount` | The receiver is owed more, or owes less |

After all transactions, only non-zero balances matter.

## Algorithm

Compute net balances.

Build an array:

```python
debts
```

containing only non-zero balances.

Then run:

```python
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:

```python
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:

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

Net balances:

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

So:

```python
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`:

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

Now the remaining problem is:

```python
[0, 5, -5]
```

Then settle `5` with `-5`.

That takes one more transaction.

Total:

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | Exponential | The DFS tries possible pairings among unsettled balances |
| Space | `O(m)` | Recursion depth and balance list |

The input constraints are small enough for this backtracking approach.

## Implementation

```python
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:

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

Then we remove people who are already settled:

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

The DFS skips zero balances:

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

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

```python
if start == len(debts):
    return 0
```

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

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

The temporary settlement is:

```python
debts[i] += debts[start]
```

This uses one transaction to eliminate `debts[start]`.

Then we recurse:

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

After recursion, we undo the change:

```python
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.

```python
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

```python
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:

| Test | Why |
|---|---|
| `[[0,1,10],[2,0,5]]` | Standard example requiring two settlements |
| Four-transaction example | Collapses to one settlement |
| Empty transactions | No debt |
| Equal opposite transactions | Already balanced |
| Chain transfer | Can be settled directly in one transaction |
| Two independent debts | Needs two transactions |