Design Algorithm to Minimize Payments in Expense-Sharing App

Scenario

Expense-sharing app needs to settle debts among friends after a trip.

Question

Given a list of transactions (payer, payee, amount), design an algorithm that produces the minimum set of payments required to settle every person’s balance.

Hints

Compute each person’s net balance, then greedily match positives with negatives using a heap or two-pointer sweep.

Minimize Payments to Settle Expenses

You are given a list of transactions, each as [payer, payee, amount], where amount is a positive integer (e.g., cents). Compute a settlement that clears every person's net balance using the minimum number of payments. First compute each person's net balance (negative = owes, positive = is owed). Then repeatedly make a payment from the person who owes the most to the person who is owed the most; transfer the smaller of the two amounts and update balances. If multiple debtors (or creditors) tie on amount, pick the lexicographically smallest name. Return the list of payments as [payer, payee, amount] in the order produced by this process.

Constraints

• 1 <= len(transactions) <= 200000
• Each transaction is [payer, payee, amount] with payer and payee as non-empty ASCII names (length 1..32)
• 1 <= amount <= 10^9 (integers)
• Number of distinct people P <= 200000
• Total of all amounts fits in 64-bit signed integer
• Output must follow the specified greedy rule; ties broken by lexicographically smallest names

Examples

Example 1

Input: transactions = [["Alice","Bob",10],["Bob","Charlie",5],["Charlie","Alice",5]]
Output: [["Alice","Bob",5]]

Explanation: Net balances: Alice -5, Bob +5, Charlie 0. Match Alice (owes 5) to Bob (is owed 5).

Example 2

Input: transactions = [["A","B",40],["A","C",10],["D","B",20],["C","D",50]]
Output: [["A","B",50],["C","B",10],["C","D",30]]

Explanation: Net: A -50, C -40, B +60, D +30. Greedy matches: A->B 50; C->B 10; C->D 30.

Hints

1. Compute each person's net balance: decrement payer by amount, increment payee by amount.
2. Maintain two max-heaps: one for creditors (positive balance) and one for debtors (absolute value of negative balance).
3. At each step, pop the largest debtor and largest creditor, transfer the smaller amount, and push back any remainder.
4. Break ties on equal amounts by lexicographically smallest names to ensure deterministic output.

Approach

Compute each person's net balance. Use two max-heaps to always match the largest debtor with the largest creditor. Transfer the minimum of the two amounts, settle at least one party each step, and reinsert any remainder. Ties on equal amounts are resolved by heap tuple ordering using names, ensuring deterministic output. This greedy strategy yields the minimum number of payments.

• Time complexity: O(T + P log P)
• Space complexity: O(P)