Compute transfers to balance account debts

Problem: Balance accounts by generating transfers

You are given a dictionary/map balances from accountId -> netBalance.

• A positive balance means the account should receive money (is owed money).
• A negative balance means the account should pay money (owes money).
• The sum of all balances is guaranteed to be 0.

Produce a list of transfers that will settle all accounts to net 0.

Output format

Return a list of transfers like:

• (fromAccount, toAccount, amount) where amount > 0

After applying all transfers:

• Every account’s balance becomes exactly 0.

Example

Input:

{ A: -5, B: 2, C: 3 }

One valid output:

[(A, B, 2), (A, C, 3)]

Notes / constraints

• You may return any valid set of transfers.
• Prefer fewer transfers if possible, but correctness is the priority.

Compute Transfers to Balance Account Debts

You are given a map balances from accountId -> netBalance.

• A positive balance means the account should receive money (is owed money).
• A negative balance means the account should pay money (owes money).
• The sum of all balances is guaranteed to be 0.

Produce a list of transfers (fromAccount, toAccount, amount) with amount > 0 such that, after applying all transfers, every account's balance becomes exactly 0.

Example

Input: {A: -5, B: 2, C: 3}

One valid output: [(A, B, 2), (A, C, 3)]

Canonical (deterministic) output used by this console

To make the answer reproducible, sort the debtors (accounts that owe money) and the creditors (accounts owed money) by accountId, then greedily match the smallest-id debtor against the smallest-id creditor, emitting a transfer of min(owed, owedTo) and advancing whichever side reaches 0. Continue until all balances settle. This yields at most n - 1 transfers for n non-zero accounts.

Notes / constraints

• Any valid set of transfers settles the accounts; this console grades against the canonical sorted-greedy output above.
• Accounts with a balance of 0 need no transfer.
• An empty map yields an empty transfer list.

Hints

1. Split accounts into debtors (negative balance) and creditors (positive balance); the absolute owed amount equals the magnitude of the balance.
2. Sort both groups by accountId so the matching order is deterministic and reproducible.
3. Use two pointers: transfer min(debtorOwed, creditorOwed) from the current debtor to the current creditor, subtract it from both, and advance whichever side hits 0.
4. Stop when either group is exhausted; because the total sums to 0, both finish together.