406. Minimise the Cash Flow Among a Set of Friends

n friends (0-indexed) have lent each other money, given as an n x n matrix graph where graph[i][j] is the amount friend i owes friend j directly (0 if none). Settle all debts with the minimum-transaction greedy approach: repeatedly find the friend with the maximum net credit and the friend with the maximum net debit (ties broken by the smaller index), have the debtor pay the creditor min(credit, -debit), and repeat until everyone's net balance is 0. Print each transaction as 'debtor creditor amount', one per line, in the order performed; print 'No transactions needed' if every net balance is already 0.

Input: The first line contains an integer n, the number of friends. Each of the next n lines contains n space-separated integers, the i-th line giving graph[i][0..n-1], the amount friend i owes each other friend. Output: Print each transaction as 'debtor creditor amount', one per line in the order performed, or print 'No transactions needed' if every net balance is already 0.

1 <= n <= 20

This is the matrix-based version of 'Minimize Cash Flow Among Friends' from the Greedy category - the same underlying settlement technique, just starting from a full pairwise debt matrix that needs to be reduced to net balances first.

Given a matrix of who-owes-whom-how-much, settle everyone's debts with the fewest transactions. Brute force: Try every possible sequence of pairwise settlements directly, searching for the fewest transactions - this is combinatorially expensive to search exhaustively, when the greedy largest-creditor-vs-largest-debtor rule directly matches this problem's own defined procedure. Optimised: Reducing the full pairwise debt matrix down to just each person's NET balance FIRST is the key simplification - the actual pairwise debt DETAILS don't matter for the settlement structure, only each person's overall net position does, and settling between the largest creditor/debtor at each step guarantees at least one balance zeros out per transaction.

Compute each friend's net balance once up front as (sum of money owed to them) minus (sum of money they owe), an O(n^2) pass over the matrix. Then repeat: scan the balance array linearly to find the max positive (creditor) and max negative (debtor, by magnitude), settle min(credit, debt) between them by updating just those two entries in O(1), and record the transaction; stop when all balances are zero. Maintaining the balances incrementally instead of rederiving them removes the repeated matrix rescans of the brute approach. Time: O(n^2) Space: O(n)

Keep the same incrementally-maintained net balance array, but instead of a linear scan to find the extremes each round, maintain a max-heap of creditors and a max-heap of debit magnitudes (with index as tiebreaker), so the current maximum creditor and maximum debtor can be found in O(log n) rather than O(n). After settling a transaction, push the updated (possibly still nonzero) balances back onto the heaps. This trades a small heap-maintenance overhead for faster extreme lookups each round, which matters as the number of friends grows. Time: O(n^2 log n) Space: O(n)

On every round, recompute every friend's net balance completely from scratch straight from the original graph matrix combined with all transactions settled so far (i.e. re-derive, don't maintain, the running state), then linearly scan all n balances to find the maximum creditor and maximum debtor (breaking ties by smaller index), and perform that one transaction. Repeating this full O(n^2) recomputation for up to n-1 rounds is correct but wasteful, since almost all of that recomputed state didn't change between rounds. Time: O(n^3) Space: O(n^2)

1. First reduce the whole matrix to each friend's single NET amount: net[i] = (total owed TO i) - (total i owes others) - the transaction structure only depends on these net balances, not the original pairwise debts. 2. At each step, the friend with the LARGEST positive net (owed the most overall) receives money directly from the friend with the LARGEST negative net (owing the most overall). 3. Settle exactly min(that credit, that debit) between them, update both, and repeat until every net balance is 0.

Time: O(n²) - computing net balances from the matrix takes O(n²), and finding the largest creditor/debtor at each of up to n-1 steps costs O(n) with a linear scan. Space: O(n), for the net balance array.

a matrix where all net balances are already zero (print 'No transactions needed'), n = 1, and n at its maximum of 20 with debts owed in both directions between the same pair.

Be ready to explain that this greedy approach doesn't ALWAYS produce the mathematically FEWEST possible transactions in theory (a cleverer grouping could sometimes do better) - but it's the standard, deterministic algorithm this specific problem defines and always terminates correctly.