Settle debts with minimal transactions

You are given a list of debts among a set of people, expressed as triples (debtor, creditor, amount) (equivalently (payer, payee, amount)), where each amount is a positive integer. Return a set of settlement transfers (from, to, amount) that clears every participant's net balance using the minimum possible number of transactions. If several optimal solutions exist, return any one of them.

Your answer should cover the full pipeline:

• Reduce to net balances. Collapse the raw debts to each person's net balance (total owed-to-them minus total they owe). People whose net balance is zero are already settled and can be ignored.
• Settle with the fewest transfers. Produce a sequence of transfers that zeroes out all remaining (non-zero) balances using the minimum number of transactions.
• Justify it. Describe the method, argue correctness, and analyze time and space complexity. Account for large intermediate balances (overflow) and the sum-to-zero invariant.

Hint: Where to start

The raw (payer, payee, amount) edges carry no information beyond each person's net position. Collapse them first: bal[person] += received - paid. Drop everyone with bal == 0. Now you only have a multiset of non-zero signed balances to clear.

Hint: Reframe as zero-sum groups

If you can split the $m$ non-zero balances into $g$ disjoint groups that each sum to zero, a group of size $k$ needs exactly $k-1$ transfers, so the total is $m - g$. Minimizing transfers is equivalent to maximizing the number of zero-sum groups $g$. A trivial settlement gives $g=1$ (i.e. $m-1$ transfers); the optimum may do much better.

Hint: Search technique

With $N$ small (~20), finding the maximum number of zero-sum groups is the hard core (it is NP-hard in general — a partition-style problem). Use backtracking with pruning: at each step take the first non-zero balance and try to cancel it against every later balance of the opposite sign, recurse, keep the minimum. Prune by skipping duplicate balance values, and short-circuit when you find an exact-opposite partner ($\text{debt}[i] = -\text{debt}[\text{start}]$) — pairing exact opposites is always at least as good.

Hint: Faster fallback

For large or skewed $N$ where exponential search is too slow, a two-heap greedy (largest creditor against largest debtor, push back the remainder) settles in $O(m \log m)$ — valid but not always minimal, since it never splits an amount to form a zero-sum subset. Flag it as a heuristic, not optimal.

Constraints & Assumptions

• Each input amount is a positive integer; the same pair may appear multiple times.
• Basic version: up to about 20 distinct people with non-zero net balance (so exponential-but-pruned search is acceptable).
• The signed net balances of all participants must sum to exactly 0; otherwise the input is inconsistent.
• Net balances can grow large after consolidation — assume they may exceed a single edge amount and require 64-bit accumulators.
• A transfer amount must be a positive integer; you do not get partial-cent rounding issues (all amounts are integers).

Clarifying Questions to Ask

• Do I need to return the actual list of transfers (from, to, amount), or only the minimum count of transactions?
• Can the same (debtor, creditor) pair appear more than once in the input, and can a person be both a debtor and a creditor across different edges?
• Is N truly bounded at ~20, or should I design for thousands of people (which changes the algorithm from exact to heuristic)?
• Are negative or zero amounts possible in the input, and is the input guaranteed to be self-consistent (balances sum to zero)?
• How large can individual amounts and accumulated balances get — do I need to worry about 32-bit overflow?

What a Strong Answer Covers

• Reduction insight: recognizing that the raw edges are irrelevant once you compute each person's net balance, and that only non-zero balances participate.
• Optimality framing: the $m - g$ formulation (transfers = people minus number of zero-sum groups), and an explanation of why the trivial $m-1$ bound is not always tight.
• Exact algorithm: correct backtracking that cancels balances against opposite-sign partners, with duplicate-skipping and exact-opposite pruning, plus how to recover the transfer list (not just the count).
• Complexity & correctness: a justification that backtracking explores all cancellation orderings and so finds the minimum, with explicit time/space bounds for the reduction, the exact search, and the greedy fallback.
• Robustness: the sum-to-zero sanity check, 64-bit / arbitrary-precision accumulators for large intermediates, and handling of already-settled (zero-balance) people.
• Scale awareness: the difference between the exact method (small $N$) and the heap-based greedy heuristic (large or skewed $N$), stated honestly as a trade-off.

Follow-up Questions

• How would you modify the algorithm to also return one concrete optimal transfer list, and how do you reconstruct it from the recursion?
• Suppose N is in the thousands. What do you ship instead, and what is the worst-case gap between the greedy heuristic and the true optimum?
• If amounts were arbitrary decimals (e.g. currency with cents), what changes — and how do you avoid floating-point drift in the sum-to-zero check?
• Can you give a quick proof that a connected zero-sum group of $k$ people can always be settled in exactly $k-1$ transfers, and never fewer?

Solution

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.

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.

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.

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:

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.

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.

Debts (a->b 10), (b->c 10) reduce to net balances {a:-10, c:+10} and settle in 1 transfer (a->c 10). Debts (a->b 5),(b->c 5),(c->a 5) all net to zero and require 0 transfers. A graph of 4 people that splits into two zero-sum pairs settles in 2 transfers, not 3.