Minimize Cash Flow among a given set of friends who have borrowed money from each other Hard 0 attempts
GeeksforGeeks ↗

Minimize Cash Flow among a given set of friends who have borrowed money from each other

Hard GraphBFSDFS GeeksforGeeks

You're given a group of N friends along with a matrix describing how much each one owes the others. Work out a way to settle every debt using as few individual payments as possible.

Input Format
Implement minCashFlow(graph). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 · Run Sample

Input
graph = [[0,1000,2000],[0,0,5000],[0,0,0]]
Output
[[1,2,4000],[0,2,3000]]

Example 2

Input
graph = [[0,0],[0,0]]
Output
[]

Example 3

Input
graph = [[0,0,0,0,8,0,0],[0,0,0,0,1,6,0],[0,0,0,0,0,2,4],[0,0,0,0,0,0,5],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]
Output
[[0,5,8],[1,4,7],[2,4,2],[2,6,4],[3,6,5]]

Explanation: Net balances are [-8,-7,-6,-5,9,8,9]. Settle the matching 8-unit pair first, then settle the remaining five non-zero balances in four payments. Five payments are optimal; matching the largest debtor and creditor greedily needs six.

Constraints
  • 1 <= N <= 10
  • graph is an N × N matrix of non-negative integer debts
  • Each debt and every net balance are safe JavaScript integers.
Test Cases (3)
Case 1
Args: [[[0,1000,2000],[0,0,5000],[0,0,0]]] Expected: [[1,2,4000],[0,2,3000]]
Case 2
Args: [[[0,0],[0,0]]] Expected: []
Case 3
Args: [[[0,0,0,0,8,0,0],[0,0,0,0,1,6,0],[0,0,0,0,0,2,4],[0,0,0,0,0,0,5],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,0,0]]] Expected: [[0,5,8],[1,4,7],[2,4,2],[2,6,4],[3,6,5]]
Topics
GraphBFSDFS

Backtracking on Net Balances

First cancel each person's incoming and outgoing debts. Skip settled people, then pair the first unsettled balance with each opposite-sign balance. Transfer the first person's full remaining balance and recurse; the counterpart may become a debtor or creditor. Keep the settlement with the fewest payments. This exhaustive search includes an optimal settlement, unlike repeatedly matching the largest debtor and creditor.

javascript
function minCashFlow(graph) {
  const n = graph.length, net = Array(n).fill(0);
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
    net[i] -= graph[i][j]; net[j] += graph[i][j];
  }
  let best = null;
  function search(start, payments) {
    while (start < n && net[start] === 0) start++;
    if (start === n) { if (!best || payments.length < best.length) best = payments.slice(); return; }
    if (best && payments.length >= best.length) return;
    const balance = net[start], tried = new Set();
    for (let j = start + 1; j < n; j++) {
      if (net[j] * balance >= 0 || tried.has(net[j])) continue;
      tried.add(net[j]);
      const previous = net[j]; net[j] += balance;
      payments.push(balance < 0 ? [start, j, -balance] : [j, start, balance]);
      search(start + 1, payments);
      payments.pop(); net[j] = previous;
      if (previous + balance === 0) break;
    }
  }
  search(0, []);
  return best || [];
}

Time: O(N² + N!) as a loose upper bound. Space: O(N) auxiliary space, excluding the input matrix.

Saved in this browser only. Private to you.

JavaScript