Minimise cash flow among friends
Problem
graph[i][j] is how much person i owes person j. Settle every debt using the fewest transactions (or the smallest total amount moved), by working out each person's net balance.
Example 1
Input: [[0,1000,2000], [0,0,5000], [0,0,0]] Output: Person 1 pays 4000 to person 2; person 0 pays 3000 to person 2
Also asked as: Minimise the cashflow among a given set of friends who have borrowed money from each other · Minimize Cash Flow among a given set of friends who have borrowed money from each other
Test cases
No automated tests for this problem yet. Use the examples above to check your output.
This problem has no automated tests. Run executes your code and shows what it logs.
View solutionHide solution1 approach
1. Net balance per person, greedily settle max creditor with max debtor
Time O(n²)Space O(n)
Compute each person’s net (received − paid). Repeatedly pick the biggest positive and biggest negative balance; settle min(|a|, |b|); repeat until all are zero.
function minCashFlow(graph) { // graph[i][j] = amount i owes j const n = graph.length; const net = new Array(n).fill(0); for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) { net[i] += graph[j][i]; net[i] -= graph[i][j]; } const txns = []; const settle = () => { let mxCredit = net.indexOf(Math.max(...net)); let mxDebit = net.indexOf(Math.min(...net)); if (net[mxCredit] === 0 && net[mxDebit] === 0) return; const amt = Math.min(-net[mxDebit], net[mxCredit]); net[mxCredit] -= amt; net[mxDebit] += amt; txns.push([mxDebit, mxCredit, amt]); settle(); }; settle(); return txns;}