GreedyProblem 11 of 35
Minimize Cash Flow among a given set of friends who have borrowed money from each other
Problem Statement
Given a number of friends who have to give or take some amount of money from one another, find a way to minimize the total cash flow among all friends.
Given a 2D array transaction[n][n] where transaction[i][j] represents the amount that friend i needs to pay to friend j.
Constraints:
- 1 ≤ n ≤ 100
- 0 ≤ transaction[i][j] ≤ 10^6
Example:
- Input: 3 friends with transactions:
- Friend 0 pays Friend 1: 1000
- Friend 1 pays Friend 2: 5000
- Friend 2 pays Friend 0: 2000
- Output: Minimize transactions by settling net amounts
- Friend 1 pays Friend 2: 4000
- Friend 0 pays Friend 2: 1000
Approach 1: Brute Force (Try All Settlement Orders)
Intuition
Calculate net amount for each person, then try all possible orders of settlement to minimize transactions.
Algorithm
- Calculate net amount for each person (credit - debit)
- Try all permutations of people to settle
- For each permutation, simulate settlement and count transactions
- Track minimum transactions
java
import java.util.*;
public class Solution {
private int minTransactions = Integer.MAX_VALUE;
private void settle(int[] net, int idx, int count) {
while (idx < net.length && net[idx] == 0) idx++;
if (idx == net.length) {
minTransactions = Math.min(minTransactions, count);
return;
}
for (int j = idx + 1; j < net.length; j++) {
if (net[j] * net[idx] < 0) {
net[j] += net[idx];
settle(net, idx + 1, count + 1);
net[j] -= net[idx];
}
}
}
public int minimizeCashFlow(int[][] transactions) {
int n = transactions.length;
int[] net = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
net[i] -= transactions[i][j];
net[j] += transactions[i][j];
}
}
minTransactions = Integer.MAX_VALUE;
settle(net, 0, 0);
return minTransactions;
}
}Complexity Analysis
- Time Complexity: O(n! * n) - Trying all possible orderings
- Space Complexity: O(n) - Recursion stack
Approach 2: Greedy (Max Creditor to Max Debtor) - Optimal
Intuition
Repeatedly find the person with maximum credit and the person with maximum debt, then settle between them. This minimizes the number of transactions.
Algorithm
- Calculate net amount for each person
- Find max creditor and max debtor
- Settle the minimum of their amounts
- Update net amounts
- Repeat until all settled
java
import java.util.*;
public class MinimizeCashFlow {
private int getMaxCredit(int[] net) {
int maxIdx = 0;
for (int i = 1; i < net.length; i++) {
if (net[i] > net[maxIdx]) maxIdx = i;
}
return maxIdx;
}
private int getMaxDebit(int[] net) {
int minIdx = 0;
for (int i = 1; i < net.length; i++) {
if (net[i] < net[minIdx]) minIdx = i;
}
return minIdx;
}
public List<int[]> minimize(int[][] graph) {
int n = graph.length;
// Calculate net amount
int[] net = new int[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
net[i] += graph[j][i] - graph[i][j];
}
}
List<int[]> transactions = new ArrayList<>();
while (true) {
int maxCredit = getMaxCredit(net);
int maxDebit = getMaxDebit(net);
if (net[maxCredit] == 0 && net[maxDebit] == 0) break;
int settle = Math.min(net[maxCredit], -net[maxDebit]);
net[maxCredit] -= settle;
net[maxDebit] += settle;
transactions.add(new int[]{maxDebit, maxCredit, settle});
}
return transactions;
}
public void printSolution(int[][] graph, String[] names) {
System.out.println("Original transactions:");
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph.length; j++) {
if (graph[i][j] > 0) {
System.out.printf(" %s owes %s: $%d%n",
names[i], names[j], graph[i][j]);
}
}
}
List<int[]> transactions = minimize(graph);
System.out.println("\nOptimized transactions:");
for (int[] t : transactions) {
System.out.printf(" %s pays %s: $%d%n",
names[t[0]], names[t[1]], t[2]);
}
System.out.printf("\nTotal transactions: %d%n", transactions.size());
}
public static void main(String[] args) {
MinimizeCashFlow mcf = new MinimizeCashFlow();
int[][] graph = {
{0, 1000, 0},
{0, 0, 5000},
{2000, 0, 0}
};
String[] names = {"Alice", "Bob", "Charlie"};
mcf.printSolution(graph, names);
}
}Dry Run Example
Friends: Alice (0), Bob (1), Charlie (2)
Original transactions:
- Alice pays Bob: 1000
- Bob pays Charlie: 5000
- Charlie pays Alice: 2000
Calculate net amounts:
Alice: receives 2000, pays 1000 → net = +1000 (creditor)
Bob: receives 1000, pays 5000 → net = -4000 (debtor)
Charlie: receives 5000, pays 2000 → net = +3000 (creditor)
Step 1:
Max creditor: Charlie (+3000)
Max debtor: Bob (-4000)
Settle: min(3000, 4000) = 3000
Bob pays Charlie: 3000
net[Charlie] = 3000 - 3000 = 0
net[Bob] = -4000 + 3000 = -1000
Updated net: Alice=+1000, Bob=-1000, Charlie=0
Step 2:
Max creditor: Alice (+1000)
Max debtor: Bob (-1000)
Settle: min(1000, 1000) = 1000
Bob pays Alice: 1000
net[Alice] = 1000 - 1000 = 0
net[Bob] = -1000 + 1000 = 0
Updated net: Alice=0, Bob=0, Charlie=0
All settled!
Result:
1. Bob pays Charlie: $3000
2. Bob pays Alice: $1000
Original: 3 transactions
Optimized: 2 transactions
Complexity Analysis
- Time Complexity: O(n^2) per settlement, maximum n-1 settlements = O(n^3)
- Space Complexity: O(n) for net array + O(n) for result
Using Heap for Optimization
Key Takeaways
- Net Amount Calculation: For each person, net = total received - total paid
- Greedy Matching: Match max creditor with max debtor
- Settle Minimum: Transfer the minimum of their amounts
- Maximum n-1 Transactions: With n people, at most n-1 transactions needed
- Proof of Optimality: Each transaction settles at least one person
- Heap Optimization: Use heaps for O(n log n) per settlement
- Real Application: Splitwise, group expense settlement
- Graph Interpretation: Cash flow as directed weighted graph