Low Level Design: Splitwise with Debt Simplification Graph Algorithm

1. Problem Scope & Split Types

Splitwise lets groups of friends record expenses and split costs. Expenses can be split in multiple ways: Equal Split, Exact Amount Split, and Percentage Split. The system must validate that the sum of splits matches the total expense exactly.

2. Object-Oriented Hierarchy: Strategy Pattern for Splits

We define an abstract `Expense` base class with concrete subclasses (`EqualExpense`, `ExactExpense`, `PercentExpense`). Each split type implements a `validate()` method to enforce business invariants before recording balances in the ledger.

3. The Debt Simplification Graph Algorithm

If User A owes User B $20, and User B owes User C $20, User A should pay User C $20 directly, eliminating User B from the transaction. This is the classic Min-Cash-Flow problem.

We compute net balances for every user: `netAmount = totalCredit - totalDebit`. We separate users into net creditors and net debtors, then greedily settle the maximum debtor with the maximum creditor using a two-pointer or heap approach in $O(N \log N)$ time.

interface Split {
  userId: string;
  amount: number;
}

class ExpenseManager {
  private balances = new Map<string, Map<string, number>>();

  public addExpense(paidBy: string, amount: number, splits: Split[]) {
    for (const split of splits) {
      if (split.userId === paidBy) continue;
      this.updateBalance(paidBy, split.userId, split.amount);
    }
  }

  private updateBalance(creditor: string, debtor: string, amount: number) {
    if (!this.balances.has(creditor)) this.balances.set(creditor, new Map());
    const current = this.balances.get(creditor)!.get(debtor) || 0;
    this.balances.get(creditor)!.set(debtor, current + amount);
  }
}