Simplify debts algorithm in LLD - System Design Guide

Problem Statement

When multiple people owe each other money in a group, manually figuring out who should pay whom and how much becomes confusing and error-prone. This leads to unnecessary transactions, wasted time, and frustration among friends or colleagues.

Solution

The algorithm calculates the net amount each person owes or is owed by summing all debts. It then matches people who owe money with those who should receive money, minimizing the number of transactions needed to settle all debts. This reduces complexity and simplifies payments.

Architecture

Input:

Debts list ─┼──────▶

→net balances ─┼──────▶

↓

Output:

Output:

This diagram shows the flow from input debts, calculating net balances, matching debts to minimize transactions, and producing a simplified payment list.

Trade-offs

✓ Pros

→

Reduces the total number of transactions needed to settle debts.

→

Simplifies complex debt relationships into clear payments.

→

Saves time and reduces errors in manual calculations.

→

Improves fairness by balancing net owed amounts.

✗ Cons

→

Algorithm complexity grows with the number of participants.

→

May require iterative matching which can be computationally expensive for very large groups.

→

Does not handle partial payments or time-based priorities without extensions.

Use when a group has multiple debts among members and wants to minimize the number of payments, especially when the group size is moderate (up to a few hundred participants).

Avoid when debts are simple (few participants or few debts), or when partial/time-prioritized payments are required without additional logic.

Real World Examples

Splitwise

Simplifies group expenses by calculating net balances and minimizing payments among friends sharing costs.

Venmo

Uses similar logic to suggest simplified payments between users who owe each other money.

Airbnb

When multiple guests share costs, Airbnb simplifies who pays whom to settle group bills efficiently.

Code Example

The before code pays each debt individually, causing many transactions. The after code calculates net balances per person, then matches debtors and creditors to minimize payments, reducing the total transactions.

LLD

### Before: naive approach - pay each debt separately

def naive_settlement(debts):
    payments = []
    for debtor, creditor, amount in debts:
        payments.append((debtor, creditor, amount))
    return payments


### After: simplified debts algorithm - minimize transactions

def simplify_debts(debts):
    from collections import defaultdict

    net_balance = defaultdict(int)
    for debtor, creditor, amount in debts:
        net_balance[debtor] -= amount
        net_balance[creditor] += amount

    debtors = []
    creditors = []
    for person, balance in net_balance.items():
        if balance < 0:
            debtors.append([person, -balance])  # owes money
        elif balance > 0:
            creditors.append([person, balance])  # to receive money

    payments = []
    i, j = 0, 0
    while i < len(debtors) and j < len(creditors):
        debtor, debt_amount = debtors[i]
        creditor, credit_amount = creditors[j]
        settled_amount = min(debt_amount, credit_amount)
        payments.append((debtor, creditor, settled_amount))
        debtors[i][1] -= settled_amount
        creditors[j][1] -= settled_amount

        if debtors[i][1] == 0:
            i += 1
        if creditors[j][1] == 0:
            j += 1

    return payments

Alternatives

Greedy settlement

Matches the largest debtor with the largest creditor iteratively without global optimization.

Use when: When a fast, simple solution is needed and the group size is small.

Graph cycle cancellation

Detects cycles in debt graph and cancels them out to reduce transactions.

Use when: When debts form complex cycles and you want to optimize transaction count further.

Summary

Simplify debts algorithm reduces the number of payments needed to settle debts among a group.

It calculates net balances and matches debtors with creditors to minimize transactions.

This approach saves time, reduces errors, and clarifies who pays whom.