LeetCode 465 - Optimal Account Balancing
The problem gives a list of money transfers between people. Each transaction is represented as [from, to, amount], meaning one person paid a certain amount to another person.
Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask
Solution
Problem Understanding
The problem gives a list of money transfers between people. Each transaction is represented as [from, to, amount], meaning one person paid a certain amount to another person. After all transactions are completed, some people may owe money overall, while others are owed money overall.
The goal is not to recreate the original transactions. Instead, the goal is to settle all remaining balances using the minimum possible number of new transactions.
A useful way to think about the problem is in terms of net balance. For every person:
- If their final balance is positive, they should receive money.
- If their final balance is negative, they owe money.
- If their balance is zero, they are already settled and can be ignored.
For example, if someone paid out $10 and later received $6, their final balance is -4, meaning they still owe $4 overall.
The input size is intentionally small:
- At most 8 transactions
- Person IDs range from 0 to 11
Although the number of transactions is small, the number of possible settlement combinations can still grow very quickly. This is a strong hint that exponential techniques such as backtracking, dynamic programming with bitmasks, or pruning-based search are expected.
The important observation is that only the final net balances matter. The exact sequence of original transactions is irrelevant once we compute the net debt for every person.
Several edge cases are important:
- Some people may already have zero balance after all transactions.
- Multiple transactions between the same pair of people may cancel each other out.
- The optimal solution may require combining debts in non-obvious ways.
- Greedy matching can fail because a locally optimal settlement may block a globally optimal arrangement.
- There may be many equivalent settlement orders, so pruning duplicate states is important for efficiency.
Approaches
Brute Force Approach
A brute-force solution would attempt every possible way to settle debts between people who owe money and people who should receive money.
After computing net balances, we could repeatedly choose:
- A debtor
- A creditor
- An amount to transfer
Then recursively continue until all balances become zero.
This approach is correct because it explores every possible settlement sequence, guaranteeing that the minimum transaction count will eventually be found.
However, the search space becomes enormous very quickly. Every recursive step branches into many possibilities, and many states are effectively duplicates reached through different transaction orders. Without pruning, the algorithm becomes infeasible even for relatively small inputs.
Key Insight
The crucial insight is that we only care about net balances, not the original transactions.
Suppose we have:
[-5, +5]
This clearly needs one transaction.
Similarly:
[-5, -5, +10]
needs two transactions.
This transforms the problem into:
Given a list of non-zero balances, pair debts and credits in a way that minimizes the number of settlements.
The optimal strategy uses backtracking with pruning:
- Process one unsettled balance at a time.
- Try settling it against every opposite-signed balance.
- Recursively solve the smaller subproblem.
- Skip redundant equivalent states.
Because the number of non-zero balances is small, this exponential solution becomes practical.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n!) approximately | O(n) | Tries every possible settlement ordering |
| Optimal Backtracking | O(2^n * n!) worst case, heavily pruned in practice | O(n) | Uses net balances and recursive pruning |
Algorithm Walkthrough
Step 1: Compute Net Balances
Create a hash map where:
- Sending money decreases balance
- Receiving money increases balance
For transaction [u, v, amt]:
balance[u] -= amt
balance[v] += amt
At the end:
- Negative value means debt
- Positive value means credit
Step 2: Remove Zero Balances
People whose balances are already zero do not affect the answer.
Create a list containing only non-zero balances.
For example:
[0, -5, 5, 0]
becomes:
[-5, 5]
This significantly reduces the search space.
Step 3: Start Recursive Backtracking
Define a recursive function:
dfs(start)
where start is the first unsettled balance index.
The recursion works by trying to settle the balance at start with a later balance that has the opposite sign.
Step 4: Skip Already Settled Positions
Before processing:
while balances[start] == 0:
start += 1
This avoids unnecessary recursion on already-settled accounts.
If start reaches the end of the array, all debts are settled, so return 0.
Step 5: Try Pairing with Opposite Signs
Suppose:
balances[start] = -5
We try every later index i such that:
balances[i] > 0
We temporarily settle:
balances[i] += balances[start]
This effectively transfers the debt into the later balance.
Then recursively solve the remaining balances.
Step 6: Backtrack
After recursion finishes:
balances[i] -= balances[start]
This restores the original state for the next possibility.
Backtracking is necessary because multiple settlement choices must be explored independently.
Step 7: Prune Duplicate States
A major optimization is:
if balances[i] + balances[start] == 0:
break
If one transaction completely settles both accounts, exploring other equivalent pairings is unnecessary.
This pruning dramatically improves performance.
Why it works
At every recursive step, the algorithm chooses one unsettled account and attempts all valid ways to settle it with an opposite-signed account. Since every possible settlement configuration is explored, the algorithm cannot miss the optimal solution. Backtracking guarantees correctness by restoring state after each recursive branch, while pruning removes redundant equivalent searches without excluding any optimal solution.
Python Solution
from typing import List
from collections import defaultdict
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
balance = defaultdict(int)
# Compute net balance for each person
for sender, receiver, amount in transactions:
balance[sender] -= amount
balance[receiver] += amount
# Keep only non-zero balances
debts = [amount for amount in balance.values() if amount != 0]
def dfs(start: int) -> int:
# Skip settled balances
while start < len(debts) and debts[start] == 0:
start += 1
# All settled
if start == len(debts):
return 0
min_transactions = float("inf")
for i in range(start + 1, len(debts)):
# Must have opposite signs
if debts[start] * debts[i] < 0:
# Try settling start with i
debts[i] += debts[start]
min_transactions = min(
min_transactions,
1 + dfs(start + 1)
)
# Backtrack
debts[i] -= debts[start]
# Perfect cancellation pruning
if debts[i] + debts[start] == 0:
break
return min_transactions
return dfs(0)
The implementation begins by computing net balances using a hash map. Every outgoing transaction decreases a person's balance, while every incoming transaction increases it.
After building the balance map, the code removes all zero balances because those people are already settled and do not contribute to the search.
The recursive dfs function processes one unsettled account at a time. The start pointer identifies the current account being resolved. Any already-settled positions are skipped immediately.
For every later balance with the opposite sign, the algorithm simulates a settlement by adding the current debt into that balance. This represents one transaction. The recursion then solves the smaller remaining problem.
After the recursive call completes, the state is restored through backtracking. This ensures every recursive branch operates on a clean state.
The pruning condition:
if debts[i] + debts[start] == 0:
break
detects perfect cancellation. Once such a match is found, exploring additional equivalent matches is unnecessary.
Go Solution
package main
func minTransfers(transactions [][]int) int {
balance := map[int]int{}
// Compute net balances
for _, t := range transactions {
from, to, amount := t[0], t[1], t[2]
balance[from] -= amount
balance[to] += amount
}
// Collect non-zero balances
debts := []int{}
for _, amount := range balance {
if amount != 0 {
debts = append(debts, amount)
}
}
var dfs func(int) int
dfs = func(start int) int {
// Skip settled balances
for start < len(debts) && debts[start] == 0 {
start++
}
// All settled
if start == len(debts) {
return 0
}
minTransactions := int(^uint(0) >> 1)
for i := start + 1; i < len(debts); i++ {
// Opposite signs only
if debts[start]*debts[i] < 0 {
// Try settlement
debts[i] += debts[start]
result := 1 + dfs(start+1)
if result < minTransactions {
minTransactions = result
}
// Backtrack
debts[i] -= debts[start]
// Perfect cancellation pruning
if debts[i]+debts[start] == 0 {
break
}
}
}
return minTransactions
}
return dfs(0)
}
The Go implementation follows the same logic as the Python version. A map[int]int stores net balances, and a slice stores only non-zero debts.
Go does not have built-in infinity values for integers, so the code initializes minTransactions using the maximum possible integer:
int(^uint(0) >> 1)
The recursive closure captures the debts slice directly, allowing in-place backtracking without extra allocations.
Because constraints are small, integer overflow is not a concern here.
Worked Examples
Example 1
Input:
[[0,1,10],[2,0,5]]
Step 1: Compute Net Balances
| Person | Balance Change | Final Balance |
|---|---|---|
| 0 | -10 + 5 | -5 |
| 1 | +10 | +10 |
| 2 | -5 | -5 |
Debt array:
[-5, 10, -5]
Step 2: Start Backtracking
Current state:
[-5, 10, -5]
start = 0
Try pairing -5 with 10.
After settlement:
[-5, 5, -5]
Transactions used: 1
Recursive call:
start = 1
Now pair 5 with -5.
After settlement:
[-5, 5, 0]
Transactions used: 2
All remaining balances are settled.
Answer:
2
Example 2
Input:
[[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Step 1: Compute Net Balances
| Person | Final Balance |
|---|---|
| 0 | -4 |
| 1 | +4 |
| 2 | 0 |
Debt array:
[-4, 4]
Step 2: Backtracking
Current state:
[-4, 4]
Pair them directly.
After settlement:
[-4, 0]
Transactions used:
1
All balances settled.
Answer:
1
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(2^n * n!) worst case | Backtracking explores many settlement combinations |
| Space | O(n) | Recursion depth and debt array storage |
The algorithm is exponential in the number of non-zero balances because it explores multiple pairing possibilities recursively. However, the constraints are very small, and pruning dramatically reduces the practical search space. In real execution, the solution performs efficiently for all valid inputs.
Test Cases
from typing import List
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
from collections import defaultdict
balance = defaultdict(int)
for sender, receiver, amount in transactions:
balance[sender] -= amount
balance[receiver] += amount
debts = [x for x in balance.values() if x != 0]
def dfs(start: int) -> int:
while start < len(debts) and debts[start] == 0:
start += 1
if start == len(debts):
return 0
ans = float("inf")
for i in range(start + 1, len(debts)):
if debts[start] * debts[i] < 0:
debts[i] += debts[start]
ans = min(ans, 1 + dfs(start + 1))
debts[i] -= debts[start]
if debts[i] + debts[start] == 0:
break
return ans
return dfs(0)
sol = Solution()
assert sol.minTransfers([[0,1,10],[2,0,5]]) == 2 # basic example
assert sol.minTransfers([[0,1,10],[1,0,1],[1,2,5],[2,0,5]]) == 1 # balances collapse
assert sol.minTransfers([[0,1,5]]) == 1 # single transaction
assert sol.minTransfers([[0,1,5],[1,0,5]]) == 0 # perfectly canceled
assert sol.minTransfers([[0,1,10],[1,2,10],[2,0,10]]) == 0 # cycle cancels completely
assert sol.minTransfers([[0,1,10],[2,3,10]]) == 2 # disconnected debts
assert sol.minTransfers([[0,1,10],[2,0,10]]) == 1 # direct simplification
assert sol.minTransfers([
[0,1,5],
[0,2,5],
[3,0,10]
]) == 2 # one payer settles two creditors
assert sol.minTransfers([
[0,1,1],
[2,0,1],
[1,2,1]
]) == 0 # all balances net to zero
print("All test cases passed.")
Test Case Summary
| Test | Why |
|---|---|
[[0,1,10],[2,0,5]] |
Basic non-trivial example |
[[0,1,10],[1,0,1],[1,2,5],[2,0,5]] |
Demonstrates balance collapsing |
[[0,1,5]] |
Smallest meaningful case |
[[0,1,5],[1,0,5]] |
Exact cancellation |
| Cyclic transactions | Ensures net-zero cycles are removed |
| Disconnected debts | Multiple independent settlements |
| Simplified direct settlement | Verifies optimal compression |
| One debtor to many creditors | Tests recursive branching |
| Net-zero complex cycle | Ensures correct aggregation |
Edge Cases
Completely Balanced Transactions
A common edge case occurs when all transactions cancel each other out after net balance computation.
Example:
[[0,1,5],[1,0,5]]
A naive implementation might still attempt unnecessary recursive settlements. This implementation avoids that problem by removing all zero balances before recursion begins. The debt array becomes empty, and the algorithm immediately returns 0.
Multiple Equivalent Settlement Paths
Different transaction orders can represent the same effective state.
Example:
[-5, 5, 5, -5]
Without pruning, the algorithm may repeatedly explore equivalent recursive branches, causing major performance degradation.
The perfect-cancellation pruning condition:
if debts[i] + debts[start] == 0:
break
eliminates redundant exploration while preserving correctness.
Cyclic Debt Structures
Debt cycles can confuse implementations that focus on transaction sequences instead of net balances.
Example:
0 -> 1 -> 2 -> 0
Even though multiple transactions exist, the net effect may be completely balanced.
Because this solution first computes final net balances, all cycles naturally collapse into their simplified form. This avoids unnecessary recursive work and guarantees the algorithm solves the true optimization problem rather than the original transaction graph.