Find the minimum number of payments to settle debts between users
Last updated: August 6, 2025
Quick Overview
Given a list of transactions between users (who paid whom and how much), find the minimum number of payments needed to settle all debts. This models Affirm's internal settlement optimization between merchants.
Affirm
August 6, 202514
4
3,711 solved
Given a list of transactions between users (who paid whom and how much), find the minimum number of payments needed to settle all debts. This models Affirm's internal settlement optimization between merchants.
This algorithmic problem appears in Affirm's technical phone screens. It combines graph theory with financial concepts and tests your ability to optimize real-world financial operations.
What the Interviewer Expects
- Reduce the problem to net balances first (simplify the transaction graph)
- Recognize this as a subset-sum partitioning problem for optimal solution
- Implement a greedy approximation that works well in practice
- Discuss time complexity and why optimal solution is NP-hard
- Handle edge cases: circular debts, zero balances, single user
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you handle the case where some payment channels have fees?
- Can you prove that your greedy solution is not always optimal?
- How would you extend this to minimize total amount transferred rather than number of transfers?
- How would you handle currency conversion in multi-currency settlements?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
To solve the problem of minimizing the number of payments needed to settle debts, we first need to recognize that this can be modeled as a graph where users are nodes and transactions are directed edg...
Approach
- Calculate Net Balances: Start with an array of balances initialized to 0 for each user. For each transaction (payer, payee, amount), decrement the payer's balance and increment the payee's bala...
Submit Your Answer
