Optimizing Money Transfer: Find the Minimum Number of Transactions to Settle Group Debts

Question

## Problem

A group of people have lent and borrowed money. Given a list of transactions `(payer, payee, amount)`, compute the minimum number of transfers needed to settle all debts.

```python
from typing import List, Tuple

def min_transfers(transactions: List[Tuple[str, str, int]]) -> int:
    # transactions: [(payer, payee, amount), ...]
    # return: minimum number of bank transfers to zero out all balances
    pass
```

**Example:**
```
transactions = [("A","B",10),("B","C",10),("A","C",5)]

Net balances: A=-15, B=0, C=+15
B cancels out; one transfer A->C for $15.

Output: 1
```

## Approach

1. Compute net balance for each person.
2. Remove all zero-balance people.
3. Use backtracking/DFS to find the minimum number of transfers to match creditors and debtors.

The optimal substructure: match the largest debtor with the largest creditor whenever possible.

## Follow-ups

1. Why is the greedy (largest debtor meets largest creditor) approach not always optimal?
2. What is the time complexity of the backtracking approach and when does it become intractable?
3. How would you extend this to support multiple currencies with conversion rates?
4. In a real payment app, what additional constraints (transaction limits, network fees) would change the optimal solution?

Optimizing Money Transfer: Find the Minimum Number of Transactions to Settle Group Debts

Question Details

Full Details

Topics

More from Stripe