Minimise the cashflow among a given set of friends who have borrowed money from each other
Problem Statement
Given a group of N friends who owe money to each other, minimise the total number of transactions (cash flows) needed to settle all debts. amount[i][j] means person i owes person j that amount.
Example:
- Input:
amount = [[0,1000,2000],[0,0,5000],[0,0,0]](3 friends) - Output: Minimised transactions: Person 1 pays 4000 to Person 2, Person 0 pays 3000 to Person 2 (instead of multiple small transactions)
Noob-Friendly Explanation
Imagine you and your friends went on a trip. Everyone paid for different things and now there's a mess of who owes whom. Instead of everyone paying everyone separately (lots of transactions), you can simplify it.
First, calculate how much each person should receive or pay overall (net balance). Then, match people who owe money with people who are owed money, minimising the number of payments.
For example, if A owes B $10 and B owes C $10, instead of two transactions, A can just pay C $10 directly — just one transaction!
Approach 1: Brute Force
Intuition
Process each debt individually. For every pair (i, j) where i owes j, make a direct transaction. This doesn't minimize anything but settles all debts.
Algorithm
- For each pair (i, j), if amount[i][j] > 0, create a transaction from i to j.
- Optionally simplify: if i owes j and j owes i, net them out.
import java.util.*;
public class CashFlowBrute {
public static void settle(int[][] amount) {
int N = amount.length;
// Net out mutual debts
int[][] net = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
net[i][j] = amount[i][j] - amount[j][i];
if (net[i][j] < 0) net[i][j] = 0;
}
}
System.out.println("Transactions:");
int transCount = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (net[i][j] > 0) {
System.out.println("Person " + i + " pays " + net[i][j] + " to Person " + j);
transCount++;
}
}
}
System.out.println("Total transactions: " + transCount);
}
public static void main(String[] args) {
int[][] amount = {
{0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0}
};
settle(amount);
}
}Complexity Analysis
- Time Complexity: O(N² * T) - where T is the number of transactions to process
- Space Complexity: O(N²) - for the net amount matrix
Approach 2: Optimal (Greedy using Net Amounts)
Intuition
Calculate the net amount for each person: sum of all credits minus sum of all debits. People with positive net are creditors, people with negative net are debtors. Then use a greedy approach: find the maximum creditor and maximum debtor, settle the minimum of the two, and repeat.
Algorithm
- Calculate net amount for each person:
net[i] = sum(amount[j][i]) - sum(amount[i][j])for all j. - Find the person who owes the most (max debtor, most negative net) and the person who is owed the most (max creditor, most positive net).
- Settle the minimum of |debit| and credit between them.
- Repeat until all nets are zero.
import java.util.*;
public class CashFlowOptimal {
public static void minCashFlow(int[][] amount) {
int N = amount.length;
int[] net = new int[N];
// Calculate net amount for each person
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
net[i] += amount[j][i] - amount[i][j];
}
}
System.out.println("Minimised Transactions:");
settle(net, N);
}
static void settle(int[] net, int N) {
int maxCreditor = 0, maxDebtor = 0;
for (int i = 1; i < N; i++) {
if (net[i] > net[maxCreditor]) maxCreditor = i;
if (net[i] < net[maxDebtor]) maxDebtor = i;
}
// Base case: all settled
if (net[maxCreditor] == 0 && net[maxDebtor] == 0) return;
// Settle minimum of the two
int settleAmount = Math.min(-net[maxDebtor], net[maxCreditor]);
net[maxCreditor] -= settleAmount;
net[maxDebtor] += settleAmount;
System.out.println("Person " + maxDebtor + " pays " + settleAmount + " to Person " + maxCreditor);
settle(net, N);
}
public static void main(String[] args) {
int[][] amount = {
{0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0}
};
minCashFlow(amount);
}
}Complexity Analysis
- Time Complexity: O(N²) - at each step we find max creditor and debtor in O(N), and we have at most N-1 settlements
- Space Complexity: O(N) - for the net amount array