NeetCode #708LC-465Hard1-D Dynamic Programming
← Back to All Problems#708 · #465 · Optimal Account Balancing(最优账单平衡)
📌 Problem Statement & Constraints
Given
transactions, where transactions[i] = [from, to, amount] means from paid to that amount, return the minimum number of transactions needed to settle all debts. Constraints: 1 <= transactions.length <= 8, 0 <= from, to < 12, 1 <= amount <= 100.💡 Core Algorithmic Approaches
- First compute each person's net balance: positive if they are owed money, negative if they owe.
- People with a zero net balance are already settled and can be ignored.
- Run a DFS over the non-zero balances: take the first unsettled person and try matching them against every other person with the opposite sign.
- The minimum number of transfers is the shallowest DFS branch that clears all balances.
💻 Benchmark Python3 Implementation
class Solution:
def minTransfers(self, transactions: List[List[int]]) -> int:
from collections import defaultdict
bal = defaultdict(int)
for f, t, a in transactions:
bal[f] -= a
bal[t] += a
debts = [v for v in bal.values() if v != 0]
def dfs(start: int) -> int:
while start < len(debts) and debts[start] == 0:
start += 1 # skip settled people
if start == len(debts):
return 0
best = float("inf")
for i in range(start + 1, len(debts)):
if debts[i] * debts[start] < 0: # opposite signs can settle
debts[i] += debts[start]
best = min(best, 1 + dfs(start + 1))
debts[i] -= debts[start] # backtrack
return best
return dfs(0)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n!) worst case, but the number of non-zero balances is at most 12 and the search is pruned heavily.
💾 Space Complexity
O(n): the balances and the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to backtrack: the
debts[i]update must be undone before trying the next candidate. - Matching only same-sign balances: the guard
debts[i] * debts[start] < 0ensures a transfer reduces both magnitudes. - Skipping zero balances only once: the while loop must re-skip after every recursion, which the
start + 1argument handles. - Greedily pairing the largest debtor with the largest creditor: that heuristic can use more transactions than the optimum.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.