363. Minimize Cash Flow Among Friends

n friends have lent and borrowed money among themselves, leaving each with a net balance: positive means that friend should receive that much overall, negative means they owe that much overall (all balances sum to 0). Settle everything using this procedure: repeatedly find the friend with the largest positive balance and the friend with the most negative balance (lowest index first on ties), transfer the smaller of (the creditor's balance, the debtor's debt) between them as one transaction, and update both balances; repeat until every balance is 0. Print the total number of transactions this procedure performs.

Input: The first line contains an integer n, the number of friends. The second line contains n space-separated integers, each friend's net balance (positive means owed money, negative means owing, summing to 0). Output: Print a single integer - the total number of transactions the settlement procedure performs.

1 <= n <= 100, -10^9 <= balance <= 10^9, balances sum to 0

Every single transaction fully zeros out AT LEAST one balance (whichever of the two amounts was smaller) - this guarantee is exactly why the total number of transactions is bounded by n-1, and why the procedure is guaranteed to terminate correctly.

Settle net debts among friends using the fewest transactions, always paying off the biggest creditor and debtor first. Brute force: Try every possible sequence of pairwise settlements directly, searching for the one using the fewest transactions - this is combinatorially expensive to search exhaustively, when the greedy largest-creditor-vs-largest-debtor rule directly minimizes transactions in practice for this problem's defined procedure. Optimised: Settling between the CURRENT largest creditor and largest debtor at every step guarantees that EACH transaction fully zeros out at least ONE person's balance - since every transaction eliminates at least one more 'unsettled' person from future consideration, the total transaction count is bounded and the procedure terminates efficiently.

Repeatedly scan the entire balances array from start to finish to find the index with the maximum positive balance and the index with the most negative balance (lowest index first on ties), transfer min(credit, debt) between them, update both balances, count the transaction, and repeat until every balance is 0. This directly simulates the procedure exactly as specified, but every round costs a full linear scan of all n balances even though only two of them actually change. Time: O(n^2) Space: O(1)

Keep all nonzero balances in a balanced ordered structure (such as a sorted multiset or a TreeMap keyed by balance value) that supports retrieving the current maximum and minimum, and removing or updating an entry, all in logarithmic time directly, without the stale-entry bookkeeping that lazy-deleted heaps require. Each round removes the current max creditor and max/min debtor entries, computes the transfer, and reinserts whatever balance remains for either party, giving the exact same simulated result as the heap approach but with cleaner, always-current state and no wasted pops on outdated values. Time: O(n log n) Space: O(n)

Maintain a max-heap of all positive balances (keyed by amount, with index as tiebreaker) and a max-heap of all negative balances (keyed by absolute value, same tiebreak), so each round can pop the current largest creditor and largest debtor in logarithmic time instead of a full scan. Whenever a balance changes after a transfer, push its new value back onto the appropriate heap rather than trying to update the old entry in place, and when popping, verify a popped entry still matches that person's current true balance, discarding it as stale if not (lazy deletion). Since the procedure performs at most n-1 transactions in total, the total number of heap operations stays bounded, making each round's find-the-max step much cheaper than a linear rescan. Time: O(n log n) Space: O(n)

1. Repeatedly find the friend with the LARGEST positive balance (biggest creditor) and the friend with the MOST NEGATIVE balance (biggest debtor) - break ties by lowest index. 2. Transfer the SMALLER of (the creditor's balance, the debtor's debt amount) between them as one single transaction, updating both balances. 3. Repeat until every balance is exactly 0 - count the total number of transactions performed.

Time: O(n²) in the worst case - up to n-1 transactions are needed, and finding the largest creditor/debtor at each step costs O(n) with a simple linear scan (or O(log n) with a more advanced heap-based structure). Space: O(n), for tracking every friend's current balance.

n = 1 with balance 0 (zero transactions), balances large in magnitude (up to 10^9), and n at its maximum of 100 to confirm the repeated max-creditor/max-debtor approach runs correctly.

Be ready to mention that a max-heap and min-heap (for creditors and debtors respectively) can speed up repeatedly finding the current largest creditor/debtor from O(n) per step down to O(log n), for an overall O(n log n) solution instead of O(n²).