Design Splitwise (Expense Sharing) in Java

Splitwise-style expense sharing is a favorite LLD problem because it hides two real traps: money arithmetic that must not lose a cent, and a balance model that stays consistent as expenses accumulate. It also has a natural variation point (how an expense is split) where a pattern earns its place. The steps follow the LLD interview framework.

Requirements

Functional

Users can be added. Any user can record an expense that they paid, shared among a set of participants.
Three split types: equal, exact (each participant's amount is given), and percent (each participant's share is a percentage).
The system tracks who owes whom, and can show the balance of one user against every other user.
The system can produce a simplified list of settlements: the fewest payments that clear every debt.
Amounts must add up exactly. Splits that do not sum to the total are rejected.

Non-functional and scope

Money is never a float. All amounts are integer cents.
Output is deterministic, so tests can compare it.
One currency, in memory, single threaded. Groups, comments and currency conversion are extensions.

Entities

classDiagram
    class UserId
    class Cents
    class Split {
        <<sealed interface>>
        Equal
        Exact
        Percent
    }
    class Share {
        +UserId user
        +Cents amount
    }
    class Ledger {
        -TreeMap~UserId, TreeMap~UserId, Long~~ owed
        +addExpense(payer, total, split)
        +balancesOf(user) Map
        +simplify() List~Settlement~
    }
    class Settlement {
        +UserId from
        +UserId to
        +Cents amount
    }
    Split ..> Share : computes
    Ledger ..> Split
    Ledger ..> Settlement : produces

UserId and Cents are records (modeling domains in Java): small immutable values with validation in the constructor. Split is a sealed interface because the three strategies are a closed set the product defines. The Ledger holds all state and exposes the operations.

API

Java

UserId Ledger.addUser(String name)
void Ledger.addExpense(UserId payer, Cents total, Split split)   // throws SplitException
Map<UserId, Long> Ledger.balancesOf(UserId user)                 // positive: they owe user
List<Settlement> Ledger.simplify()

Design decisions

Integer cents and remainder distribution

Splitting 100.00 three ways is 33.33 plus 33.33 plus 33.33, which loses a cent. Floating-point types make it worse, because values such as 0.1 have no exact binary form. The rule: work in integer cents, give each participant total / n, and hand the total % n leftover cents out one each to the first participants. The shares then always sum to the total.

Java

import java.util.Arrays;

public class Main {
    static long[] splitEvenly(long totalCents, int n) {
        long base = totalCents / n;
        long remainder = totalCents % n;
        var shares = new long[n];
        for (int i = 0; i < n; i++) {
            shares[i] = base + (i < remainder ? 1 : 0);
        }
        return shares;
    }

    public static void main(String[] args) {
        var shares = splitEvenly(10_000, 3);
        System.out.println(Arrays.toString(shares) + " sum " + Arrays.stream(shares).sum());
        shares = splitEvenly(5, 4);
        System.out.println(Arrays.toString(shares) + " sum " + Arrays.stream(shares).sum());
    }
}

Output

[3334, 3333, 3333] sum 10000
[2, 1, 1, 1] sum 5

Which participants receive the extra cent must be deterministic. Here it is the first ones in the given order. Percent splits use the same idea: compute each floor share, then distribute the leftover cents, so that 33.33% x 3 does not lose money either.

Split as a sealed interface, not a class hierarchy

Three fixed strategies with different input data fit a sealed interface whose record variants carry that data. One switch over the split turns (total, participants) into per-user amounts, and one validation step checks the invariant that shares sum to the total. If the product later needed user-defined strategies, this would become an open interface; until a requirement varies that way, the sealed type is simpler and the compiler checks that every variant is handled. See modeling domains in Java.

Percentages as basis points

Percent values are stored in hundredths of a percent (basis points), so 33.33% is 3333 and 100% is 10_000. That keeps them integers, and validation is an exact comparison against 10_000.

The ledger stores pairwise net debts

For each ordered pair the ledger keeps an amount: owed[a][b] = x means a owes b the amount x. Recording an expense adds each participant's share to owed[participant][payer], skipping the payer's own share. To keep the data small and a single source of truth, the ledger nets opposite entries, so only one direction per pair is ever non-zero. A TreeMap gives sorted, deterministic iteration. HashMap iteration order is unspecified, so it would make the printed output unstable.

Simplifying debts

Pairwise balances can form chains: A owes B, B owes C. Collapse the graph to net positions: each user's total received minus total owed. Then repeatedly match the largest creditor with the largest debtor and settle the smaller of their two amounts. Every step clears at least one person, so there are at most n - 1 settlements. Finding the true minimum number of payments is NP-hard in general (it contains a partition problem), so the greedy result is the standard accepted answer: at most n - 1 payments, and not always the fewest. Two PriorityQueues keep the largest creditor and debtor at the head, so the whole pass costs O(n log n).

The complete flow is shown in the next section.

Full implementation

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.TreeMap;

record UserId(int id) implements Comparable<UserId> {
    @Override
    public int compareTo(UserId other) {
        return Integer.compare(id, other.id);
    }
}

record Cents(long amount) {
    Cents {
        if (amount < 0) {
            throw new IllegalArgumentException("amount must not be negative: " + amount);
        }
    }

    String dollars() {
        return "%d.%02d".formatted(amount / 100, amount % 100);
    }
}

record Share(UserId user, Cents amount) {}

record PercentShare(UserId user, int basisPoints) {}

/** Thrown for an invalid expense. The ledger is unchanged when it is thrown. */
class SplitException extends RuntimeException {
    SplitException(String message) {
        super(message);
    }
}

sealed interface Split {
    int FULL = 10_000; // 100.00 percent in basis points

    record Equal(List<UserId> participants) implements Split {
        public Equal {
            participants = List.copyOf(participants);
        }
    }

    record Exact(List<Share> shares) implements Split {
        public Exact {
            shares = List.copyOf(shares);
        }
    }

    record Percent(List<PercentShare> shares) implements Split {
        public Percent {
            shares = List.copyOf(shares);
        }
    }

    /** Returns validated per-user amounts that sum exactly to {@code total}. */
    static List<Share> shares(Split split, Cents total) {
        return switch (split) {
            case Equal(var participants) -> {
                if (participants.isEmpty()) {
                    throw new SplitException("an expense needs participants");
                }
                var weights = new long[participants.size()];
                Arrays.fill(weights, 1);
                yield pair(participants, distribute(total.amount(), weights));
            }
            case Exact(var shares) -> {
                if (shares.isEmpty()) {
                    throw new SplitException("an expense needs participants");
                }
                long actual = shares.stream().mapToLong(s -> s.amount().amount()).sum();
                if (actual != total.amount()) {
                    throw new SplitException(
                        "exact amounts sum to %d cents, expected %d".formatted(actual, total.amount()));
                }
                yield shares;
            }
            case Percent(var shares) -> {
                if (shares.isEmpty()) {
                    throw new SplitException("an expense needs participants");
                }
                int sum = shares.stream().mapToInt(PercentShare::basisPoints).sum();
                if (sum != FULL) {
                    throw new SplitException(
                        "percentages sum to %d basis points, expected %d".formatted(sum, FULL));
                }
                var weights = shares.stream().mapToLong(PercentShare::basisPoints).toArray();
                yield pair(shares.stream().map(PercentShare::user).toList(), distribute(total.amount(), weights));
            }
        };
    }

    private static List<Share> pair(List<UserId> users, long[] amounts) {
        var out = new ArrayList<Share>();
        for (int i = 0; i < users.size(); i++) {
            out.add(new Share(users.get(i), new Cents(amounts[i])));
        }
        return out;
    }

    /** Distributes total proportionally to weights; leftover cents go to the first entries. */
    static long[] distribute(long total, long[] weights) {
        long sum = 0;
        for (long w : weights) {
            sum += w;
        }
        var shares = new long[weights.length];
        long assigned = 0;
        for (int i = 0; i < weights.length; i++) {
            shares[i] = Math.multiplyExact(total, weights[i]) / sum;
            assigned += shares[i];
        }
        long leftover = total - assigned;
        for (int i = 0; leftover > 0; i++, leftover--) {
            shares[i]++;
        }
        return shares;
    }
}

record Settlement(UserId from, UserId to, Cents amount) {}

class Ledger {
    private record Balance(UserId user, long amount) {}

    private static final Comparator<Balance> LARGEST_FIRST =
        Comparator.comparingLong(Balance::amount).reversed().thenComparing(Balance::user);

    private final Map<UserId, String> names = new TreeMap<>();
    /** owed.get(a).get(b) = cents a owes b. Only one direction per pair is non-zero. */
    private final Map<UserId, Map<UserId, Long>> owed = new TreeMap<>();
    private int nextId;

    UserId addUser(String name) {
        var id = new UserId(nextId++);
        names.put(id, Objects.requireNonNull(name));
        return id;
    }

    String name(UserId id) {
        return names.getOrDefault(id, "?");
    }

    void addExpense(UserId payer, Cents total, Split split) {
        if (total.amount() == 0) {
            throw new SplitException("amount must be positive");
        }
        var shares = Split.shares(split, total);
        if (!names.containsKey(payer)) {
            throw new SplitException("unknown user " + payer.id());
        }
        for (var share : shares) {
            if (!names.containsKey(share.user())) {
                throw new SplitException("unknown user " + share.user().id());
            }
        }
        // Validation is complete; from here the update cannot fail.
        for (var share : shares) {
            if (!share.user().equals(payer)) {
                addDebt(share.user(), payer, share.amount().amount());
            }
        }
    }

    private void addDebt(UserId debtor, UserId creditor, long amount) {
        var reverseRow = owed.computeIfAbsent(creditor, k -> new TreeMap<>());
        long reverse = reverseRow.getOrDefault(debtor, 0L);
        if (reverse >= amount) {
            if (reverse == amount) {
                reverseRow.remove(debtor);
            } else {
                reverseRow.put(debtor, reverse - amount);
            }
            return;
        }
        reverseRow.remove(debtor);
        owed.computeIfAbsent(debtor, k -> new TreeMap<>()).merge(creditor, amount - reverse, Long::sum);
    }

    /** Positive: the other user owes {@code user}. Negative: {@code user} owes them. */
    Map<UserId, Long> balancesOf(UserId user) {
        var out = new TreeMap<UserId, Long>();
        for (var entry : owed.getOrDefault(user, Map.of()).entrySet()) {
            out.merge(entry.getKey(), -entry.getValue(), Long::sum);
        }
        for (var row : owed.entrySet()) {
            var amount = row.getValue().get(user);
            if (amount != null) {
                out.merge(row.getKey(), amount, Long::sum);
            }
        }
        return out;
    }

    /** Greedy settlement of net positions: at most n - 1 payments. */
    List<Settlement> simplify() {
        var net = new TreeMap<UserId, Long>();
        for (var row : owed.entrySet()) {
            for (var entry : row.getValue().entrySet()) {
                net.merge(row.getKey(), -entry.getValue(), Long::sum);
                net.merge(entry.getKey(), entry.getValue(), Long::sum);
            }
        }
        var creditors = new PriorityQueue<>(LARGEST_FIRST);
        var debtors = new PriorityQueue<>(LARGEST_FIRST);
        net.forEach((user, value) -> {
            if (value > 0) {
                creditors.add(new Balance(user, value));
            } else if (value < 0) {
                debtors.add(new Balance(user, -value));
            }
        });
        var out = new ArrayList<Settlement>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            var creditor = creditors.poll();
            var debtor = debtors.poll();
            long pay = Math.min(creditor.amount(), debtor.amount());
            out.add(new Settlement(debtor.user(), creditor.user(), new Cents(pay)));
            if (creditor.amount() > pay) {
                creditors.add(new Balance(creditor.user(), creditor.amount() - pay));
            }
            if (debtor.amount() > pay) {
                debtors.add(new Balance(debtor.user(), debtor.amount() - pay));
            }
        }
        return out;
    }
}

public class Main {
    public static void main(String[] args) {
        var ledger = new Ledger();
        var alice = ledger.addUser("alice");
        var bob = ledger.addUser("bob");
        var carol = ledger.addUser("carol");
        var dave = ledger.addUser("dave");

        // Alice pays 100.00 for dinner, split equally among three: one cent remains.
        ledger.addExpense(alice, new Cents(10_000), new Split.Equal(List.of(alice, bob, carol)));
        // Bob pays 60.00 for a cab; exact amounts.
        var exact = new Split.Exact(List.of(
            new Share(alice, new Cents(1_500)), new Share(bob, new Cents(2_000)), new Share(dave, new Cents(2_500))));
        ledger.addExpense(bob, new Cents(6_000), exact);
        // Carol pays 30.01 for tickets; 50 / 30 / 20 percent.
        var pct = new Split.Percent(List.of(
            new PercentShare(alice, 5_000), new PercentShare(carol, 3_000), new PercentShare(dave, 2_000)));
        ledger.addExpense(carol, new Cents(3_001), pct);

        for (var user : List.of(alice, bob, carol, dave)) {
            System.out.println(ledger.name(user) + ":");
            for (var entry : ledger.balancesOf(user).entrySet()) {
                long cents = entry.getValue();
                String verb = cents > 0 ? "is owed by" : "owes";
                System.out.println("  %s %s %s".formatted(verb, ledger.name(entry.getKey()), new Cents(Math.abs(cents)).dollars()));
            }
        }

        System.out.println("simplified:");
        for (var s : ledger.simplify()) {
            System.out.println("  %s pays %s %s".formatted(ledger.name(s.from()), ledger.name(s.to()), s.amount().dollars()));
        }

        // Validation failures leave the ledger untouched.
        var bad = new Split.Exact(List.of(new Share(alice, new Cents(100)), new Share(bob, new Cents(100))));
        tryExpense(ledger, alice, 300, bad);
        tryExpense(ledger, alice, 300, new Split.Percent(List.of(new PercentShare(alice, 6_000), new PercentShare(bob, 3_000))));
        tryExpense(ledger, alice, 300, new Split.Equal(List.of(new UserId(99))));
    }

    static void tryExpense(Ledger ledger, UserId payer, long cents, Split split) {
        try {
            ledger.addExpense(payer, new Cents(cents), split);
        } catch (SplitException e) {
            System.out.println(e.getMessage());
        }
    }
}

Output

alice:
  is owed by bob 18.33
  is owed by carol 18.32
bob:
  owes alice 18.33
  is owed by dave 25.00
carol:
  owes alice 18.32
  is owed by dave 6.00
dave:
  owes bob 25.00
  owes carol 6.00
simplified:
  dave pays alice 31.00
  carol pays bob 6.67
  carol pays alice 5.65
exact amounts sum to 200 cents, expected 300
percentages sum to 9000 basis points, expected 10000
unknown user 99

Check the arithmetic against the prose. The 100.00 dinner gives shares of 33.34, 33.33, 33.33: the extra cent goes to the first participant (Alice, the payer, whose own share is skipped). Debts are then netted, so Alice and Bob end up with a single direction between them.

The properties worth naming: addExpense validates everything before any state changes; opposite debts cancel inside addDebt, so the ledger has one number per pair and one direction; and every map is a TreeMap, so the printed order is the same on every run. Math.multiplyExact in distribute throws ArithmeticException instead of wrapping silently if total * weight overflows a long.

Simplification on a chain

The greedy settlement is easiest to trust on a case with a known answer. Here A owes B 10, B owes C 10, C owes D 10: three debts collapse into one payment from A to D, and the total money moved drops from 30 to 10. The program starts from the net positions, as simplify does.

Java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

public class Main {
    record Entry(String name, long amount) {}

    static List<String> simplify(Map<String, Long> net) {
        Comparator<Entry> largestFirst = Comparator.comparingLong(Entry::amount).reversed().thenComparing(Entry::name);
        var creditors = new PriorityQueue<>(largestFirst);
        var debtors = new PriorityQueue<>(largestFirst);
        net.forEach((name, value) -> {
            if (value > 0) {
                creditors.add(new Entry(name, value));
            } else if (value < 0) {
                debtors.add(new Entry(name, -value));
            }
        });
        var out = new ArrayList<String>();
        while (!creditors.isEmpty() && !debtors.isEmpty()) {
            var c = creditors.poll();
            var d = debtors.poll();
            long pay = Math.min(c.amount(), d.amount());
            out.add("%s pays %s %d".formatted(d.name(), c.name(), pay));
            if (c.amount() > pay) {
                creditors.add(new Entry(c.name(), c.amount() - pay));
            }
            if (d.amount() > pay) {
                debtors.add(new Entry(d.name(), d.amount() - pay));
            }
        }
        return out;
    }

    public static void main(String[] args) {
        // A owes B 10, B owes C 10, C owes D 10 -> net positions
        var net = new TreeMap<String, Long>(Map.of("A", -10L, "B", 0L, "C", 0L, "D", 10L));
        simplify(net).forEach(System.out::println);
    }
}

Output

A pays D 10

Extensions

Follow-up	Approach
Groups	Add a `Group` record holding a list of members and let `Equal` take the group's members as its participants. The ledger is unchanged.
Payments and settle-up	Model a payment as an expense in reverse: `addDebt(payerOfSettlement, receiver, amount)`. The netting logic already handles it.
Multiple payers	Let an expense carry a list of payers with amounts and distribute each participant's debt across payers proportionally, with the same `distribute` helper.
Multiple currencies	Replace `Cents` with a `Money` record holding an amount and a currency, and keep one ledger per currency. Do not convert inside the ledger.
Undo or edit an expense	Store each expense with an ID and apply its inverse (`addDebt` in the opposite direction) before applying the edited version.
Concurrency	Make `addExpense` and `simplify` `synchronized`, or serialize commands through a single-thread executor. See thread-safe components.
Testing	The ledger has no clock, I/O or randomness, so unit tests need no fakes. A randomized test that expenses leave the sum of all net positions at zero is a strong invariant.

Interview points

Money is an integer count of the smallest unit. Remainder cents are handed out in a fixed order so shares sum exactly to the total.
Percentages in basis points keep validation an exact integer comparison.
One net amount per user pair, with opposite debts cancelled on arrival, keeps a single source of truth.
Greedy matching of the largest creditor with the largest debtor gives at most n - 1 settlements. The true minimum is NP-hard.
Validation runs before any mutation, so a rejected expense changes nothing.

Summary

Represent money as integer cents in a record and never use floating point. Distribute the remainder cents deterministically so shares sum exactly to the total.
Use a sealed interface for the closed set of split types. Each record variant carries its own data and one method validates and computes the shares.
Store percentages as basis points so validation is an exact integer comparison.
Keep one net amount per user pair and net opposite debts as they arrive. Validate before mutating so a rejected expense changes nothing.
Simplify by reducing to net positions and matching the largest creditor with the largest debtor, at most n - 1 payments.
Use TreeMap everywhere ordering reaches output, so results are reproducible.