## Summary The raw `(debtor, creditor, amount)` edges carry no information beyond each person's **net** position, so the first move is to collapse them. After that, the question becomes: clear a multiset of non-zero signed balances with the fewest transfers. The key insight is that **transfers = (people with non-zero balance) − (number of disjoint zero-sum groups you can carve out)**, so minimizing transfers means *maximizing zero-sum groups* — an NP-hard partition-style problem that we solve exactly with pruned backtracking at the ~20-person scale, and approximately with a two-heap greedy when `N` is large. --- ## Step 1 — Collapse to net balances Define each person's net balance as `(total owed to them) − (total they owe)`. Build it by walking the edges once. A **creditor** ends with a positive balance (must receive); a **debtor** ends negative (must pay). Anyone at exactly zero is already settled and is dropped immediately. ```python from collections import defaultdict def net_balances(debts): bal = defaultdict(int) # use 64-bit accumulators in Java/C++ for debtor, creditor, amt in debts: # amt > 0 bal[debtor] -= amt bal[creditor] += amt return bal ``` **Sanity invariant:** every dollar owed is owed *to* someone, so `sum(bal.values()) == 0` always. If it doesn't, the input is inconsistent — fail fast. Let $m$ be the number of people with a non-zero balance after this reduction. Only these $m$ people participate in any transfer. --- ## Step 2 — Why the trivial bound isn't optimal A naive settlement: repeatedly pick any debtor and any creditor, transfer `min(|debtor|, creditor)`. Each transfer zeroes at least one person, so it finishes in **at most $m - 1$ transfers**. This is a correct upper bound, but not always minimal. It misses a structural shortcut: if a *subset* of people has balances that net to zero, that subset can be settled internally without ever touching the rest. Concretely, if you can partition the $m$ non-zero balances into $g$ disjoint groups that **each sum to zero**, then a group of size $k$ needs exactly $k - 1$ transfers (one fewer transfer than people, because the last person is automatically zeroed once the others are). Summing over all groups: $$\text{total transfers} = \sum_{\text{groups}} (k_i - 1) = m - g.$$ So **minimizing transfers ⇔ maximizing the number of zero-sum groups $g$**. The trivial bound is just the $g = 1$ case ($m - 1$). Finding the maximum number of zero-sum subsets is NP-hard in general (it generalizes the partition problem), which is exactly why the small bound (~20 people) is stated and why interviewers accept exponential-but-pruned search here. --- ## Step 3 — Exact algorithm: backtracking with pruning Keep only the non-zero balances in an array `b`. Walk left to right; whenever `b[start]` is non-zero, try to cancel it against **every later balance of the opposite sign**, recurse, and keep the minimum count. Two prunes make this fast at $m \approx 20$: 1. **Exact-opposite short-circuit.** If some later `b[i] == -b[start]`, settling that pair zeroes both in one transfer; no alternative on this branch can beat it, so we stop scanning after taking it. 2. **(Optional) duplicate-value skip.** Trying two later entries with the *same* value is redundant — skip repeats with a small `seen` set. ```python def min_transactions(debts): bal = net_balances(debts) b = [v for v in bal.values() if v != 0] # non-zero balances only n = len(b) def dfs(start): while start < n and b[start] == 0: start += 1 if start == n: return 0 best = float('inf') s = b[start] for i in range(start + 1, n): if b[i] * s < 0: # opposite sign -> can cancel b[i] += s # settle `start` fully into i best = min(best, 1 + dfs(start + 1)) b[i] -= s # undo if b[i] == -s: # exact opposite: can't do better here break return best return dfs(0) ``` This returns the minimum **count**. To also return the concrete transfers, record the directed transfer before recursing and keep the list from the best branch. A transfer `(from, to, amount)` means `from` pays `to` cash, which raises `from`'s (negative) balance toward zero and lowers `to`'s (positive) balance: ```python def settle(debts): bal = net_balances(debts) people = [p for p in bal if bal[p] != 0] b = [bal[p] for p in people] n = len(b) best = {"count": float('inf'), "transfers": None} def dfs(start, acc): while start < n and b[start] == 0: start += 1 if start == n: if len(acc) < best["count"]: best["count"] = len(acc) best["transfers"] = list(acc) return if len(acc) >= best["count"]: # bound: can't improve return s = b[start] for i in range(start + 1, n): if b[i] * s < 0: # `start` settles its whole balance against i if s < 0: # start is a debtor: pays |s| to creditor i transfer = (people[start], people[i], -s) else: # start is a creditor: debtor i pays s to start transfer = (people[i], people[start], s) b[i] += s; b[start] = 0 acc.append(transfer) dfs(start + 1, acc) acc.pop() b[start] = s; b[i] -= s # undo (restore in this exact order) if b[i] == -s: break dfs(0, []) return best["count"], best["transfers"] ``` This was checked against the canonical examples (`[[0,1,10],[2,0,5]] → 2`, `[[0,1,10],[1,0,1],[1,2,5],[2,0,5]] → 1`) and stress-tested on tens of thousands of random debt graphs: every returned transfer list is positive-valued and clears all balances to zero. --- ## Step 4 — Greedy fallback for large `N` When `N` is in the thousands (or the graph is heavily skewed — a few hubs owing/owed by many), exponential search is infeasible. Use a **two-heap greedy**: a max-heap of creditors and a max-heap of debtors, both by magnitude. Repeatedly pop the largest creditor and largest debtor, transfer the smaller magnitude, and push the remainder back. ```python import heapq def settle_greedy(debts): bal = net_balances(debts) creditors = [(-v, p) for p, v in bal.items() if v > 0] # max-heap by magnitude debtors = [( v, p) for p, v in bal.items() if v < 0] heapq.heapify(creditors); heapq.heapify(debtors) transfers = [] while creditors and debtors: cv, cp = heapq.heappop(creditors) # cv negative dv, dp = heapq.heappop(debtors) # dv negative c, d = -cv, -dv pay = min(c, d) transfers.append((dp, cp, pay)) # debtor dp pays creditor cp if c - pay > 0: heapq.heappush(creditors, (-(c - pay), cp)) if d - pay > 0: heapq.heappush(debtors, (-(d - pay), dp)) return transfers ``` This always produces a **valid** settlement in $O(m \log m)$, but it is **not guaranteed minimal**: it greedily zeroes one party per step and never *splits* an amount to expose a hidden zero-sum subset, so it effectively only ever achieves $g = 1$ on the residual. Present it honestly as a fast, near-optimal heuristic — the right answer when exactness is out of budget, the wrong answer to claim as optimal. --- ## Complexity | Phase | Time | Space | |-------|------|-------| | Net-balance reduction | $O(E)$ over input edges | $O(N)$ | | Backtracking (exact) | exponential worst case; with the two prunes it is comfortably fast for $m \lesssim 20$ | $O(m)$ recursion depth | | Greedy (heuristic) | $O(m \log m)$ | $O(m)$ | The reduction dominates input size; the search dominates wall-clock for the exact path and is bounded by the small $m$. --- ## Correctness argument 1. **Reduction loses nothing.** Two debt graphs with identical per-person net balances are interchangeable — any settlement valid for one is valid for the other — because a transfer only changes net balances. So solving over net balances is equivalent to solving over the raw edges. 2. **Group structure.** Any complete settlement partitions the $m$ non-zero people into connected zero-sum groups (a group must net to zero, or some member is left non-zero). A connected zero-sum group of size $k$ needs **exactly** $k - 1$ transfers: at least $k-1$ because each transfer can fully zero out at most one new person and the group is connected; at most $k-1$ because the trivial "one debtor, one creditor" loop zeroes one person per step and the final person is forced to zero by the sum-zero property. 3. **Backtracking is exhaustive.** Fixing `start` and trying every opposite-sign partner enumerates every way `start`'s balance can be cancelled; recursion does the same for the rest. So the search reaches the partition with the maximum number of zero-sum groups, i.e. the minimum $m - g$. The exact-opposite short-circuit only discards branches provably no better than the one taken, so it preserves optimality. --- ## Edge cases & robustness - **Sum-to-zero check** up front; reject inconsistent input. - **Large intermediate balances:** consolidated balances can exceed any single edge amount, so use 64-bit accumulators (or Python's arbitrary-precision ints) to avoid overflow. - **Already-settled people** (net zero) are dropped before search, shrinking $m$. - **Repeated pairs / mixed roles:** a person can be a debtor on some edges and creditor on others; the net reduction handles this transparently. - **Integer amounts only:** all transfers come out as positive integers, so there is no rounding/penny-allocation issue. If amounts were decimals, switch the balance accumulation to integer minor units (cents) to keep the sum-to-zero test exact and avoid floating-point drift. --- ## Answers to the follow-ups - **Returning the transfer list:** track an `acc` of directed transfers during the DFS and snapshot it on each new best (the `settle` function above); reconstruct direction from the sign of the balance being settled — a negative (debtor) balance pays a positive (creditor) one. - **`N` in the thousands:** ship `settle_greedy` ($O(m \log m)$). Its worst-case gap is bounded by the number of zero-sum subsets it fails to discover; in practice it is within a small constant of optimal on realistic graphs, but you cannot claim minimality. - **Decimal currency:** convert to integer cents on input, run the same algorithm, and verify `sum == 0` in integers — never compare floats for equality. - **Why $k-1$ and never fewer:** see correctness point 2 — connectivity forces at least $k-1$, and the trivial loop achieves it, so it is tight.

The crux is recognizing that the raw (payer, payee, amount) edges don't matter — only each person's net balance does. After reducing to non-zero net balances, a trivial settlement is m-1 transfers, but the true minimum is m minus the maximum number of zero-sum subsets you can carve out, which is NP-hard in general. For the ~20-person scale, backtracking with pruning on net balances finds the optimum; a heap-based greedy is the fast, near-optimal fallback for large or skewed graphs. Candidates should also handle large intermediate balances (64-bit) and validate that signed balances sum to zero.