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.

Practice

1. What is the main goal of the Simplify debts algorithm in group expense management?

easy

A. To calculate individual spending only

B. To increase the number of transactions

C. To reduce multiple debts into fewer payments

D. To create more complex debt chains

Solution

1. Step 1: Understand the purpose of the algorithm

   The algorithm aims to make settling debts easier by reducing the number of payments needed.

2. Step 2: Identify the effect on transactions

   It simplifies the process by minimizing transactions, not increasing them.

3. Final Answer:

   To reduce multiple debts into fewer payments -> Option C

4. Quick Check:

   Simplify debts = fewer payments [OK]

Hint: Focus on reducing payments, not increasing them [OK]

Common Mistakes:

• Thinking it increases transactions
• Confusing with individual spending calculation
• Assuming it complicates debt chains

2. Which of the following is the correct way to represent a person's net balance in a debts simplification system?

easy

A. A zero value means the person neither owes nor is owed money

B. A negative value means the person is owed money

C. Net balance is always zero for all participants

D. A positive value means the person owes money

Solution

1. Step 1: Understand net balance meaning

   Positive net balance means the person should receive money; negative means they owe money.

2. Step 2: Interpret zero net balance

   If net balance is zero, the person neither owes nor is owed money.

3. Final Answer:

   A zero value means the person neither owes nor is owed money -> Option A

4. Quick Check:

   Zero net balance = no debt [OK]

Hint: Zero net balance means no money owed or owed to you [OK]

Common Mistakes:

• Mixing positive and negative meanings
• Assuming net balance is always zero
• Confusing who owes and who is owed

3. Given the net balances: Alice: +50, Bob: -30, Charlie: -20, what is the minimum number of transactions to settle debts using the simplify debts algorithm?

medium

A. 2 transactions

B. 3 transactions

C. 1 transaction

D. 4 transactions

Solution

1. Step 1: Analyze net balances

   Alice is owed 50, Bob owes 30, Charlie owes 20.

2. Step 2: Match debtors with creditor

   Bob pays Alice 30, Charlie pays Alice 20, totaling 2 transactions.

3. Final Answer:

   2 transactions -> Option A

4. Quick Check:

   Sum debts to creditor = 2 transactions [OK]

Hint: Match debtors to creditors directly to minimize transactions [OK]

Common Mistakes:

• Counting each debt separately without simplification
• Assuming one transaction can cover all debts
• Misallocating amounts between participants

4. In the following code snippet for simplifying debts, what is the error?

net_balances = {"A": 40, "B": -40}
for person, balance in net_balances.items():
    if balance > 0:
        print(f"{person} owes money")
    else:
        print(f"{person} is owed money")

medium

A. The loop should use net_balances.keys() instead of items()

B. The condition for owing money is reversed

C. The print statements are missing parentheses

D. The dictionary keys should be integers, not strings

Solution

1. Step 1: Check condition logic

   Positive balance means the person is owed money, not owes money.

2. Step 2: Verify print statements

   Print syntax is correct; keys as strings are valid in Python.

3. Final Answer:

   The condition for owing money is reversed -> Option B

4. Quick Check:

   Positive balance = owed money, not owes [OK]

Hint: Positive balance means you get money, not owe it [OK]

Common Mistakes:

• Confusing who owes and who is owed
• Incorrect loop usage assumptions
• Syntax errors that don't exist here

5. You have a group with net balances: Dave: +70, Emma: -50, Frank: -20. How would you apply the simplify debts algorithm to minimize transactions and what are the transactions?

hard

A. Emma pays Frank 20, Frank pays Dave 50 (2 transactions)

B. Dave pays Emma 50, Dave pays Frank 20 (2 transactions)

C. Emma pays Dave 70, Frank pays Emma 0 (2 transactions)

D. Emma pays Dave 50, Frank pays Dave 20 (2 transactions)

Solution

1. Step 1: Identify creditors and debtors

   Dave is owed 70, Emma owes 50, Frank owes 20.

2. Step 2: Match debtors to creditor to minimize transactions

   Emma pays Dave 50, Frank pays Dave 20, totaling 2 transactions.

3. Final Answer:

   Emma pays Dave 50, Frank pays Dave 20 (2 transactions) -> Option D

4. Quick Check:

   Debtors pay creditor directly = 2 transactions [OK]

Hint: Debtors pay creditor amounts equal to their debts [OK]

Common Mistakes:

• Reversing payer and receiver roles
• Assigning incorrect amounts
• Adding unnecessary transactions