Show problems as
Classic problem #465HardArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Optimal Account Balancing

Real-world version: Settle the Makerspace Books
Tracked in this browser only
Read Optimal Account Balancing on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A shared makerspace keeps a log of who covered whose costs. Every element of transactions is a triple [a, b, amount], meaning member a put up amount credits towards a bill that belonged to member b. Member b is therefore short that many credits and member a is ahead by the same.

At the end of the term the books are closed. The log fixes every member's net position: a member is up by the credits they fronted for others and down by the credits others fronted for them. To close the books, credits are moved one transfer at a time. A transfer sends any amount you like from one member to another and does not have to mirror a log entry.

Return the smallest number of transfers that leaves every member with a net position of zero. Members whose position is already zero need no transfer at all.

Examples

Example 1

Input
transactions = [[0,1,20],[2,1,5]]
Output
2

Member 0 is up 20, member 2 is up 5 and member 1 is down 25. Two transfers zero everyone: member 1 sends 20 to member 0 and 5 to member 2.

Example 2

Input
transactions = [[0,1,15],[1,2,15]]
Output
1

Member 1 fronted 15 and had 15 fronted for them, so their position is already zero. One transfer of 15 credits from member 2 to member 0 closes the books.

Example 3

Input
transactions = [[1,6,7],[3,0,5],[4,0,4],[2,6,10]]
Output
4

Positions are +7 for member 1, +10 for member 2, +5 for member 3, +4 for member 4, -9 for member 0 and -17 for member 6. Four transfers zero them all: member 6 sends 7 to member 1 and 10 to member 2, and member 0 sends 5 to member 3 and 4 to member 4.

Example 4

Input
transactions = [[0,1,10],[1,0,10]]
Output
0

The two entries cancel, so both members finish at zero and nothing needs to move.

Constraints

  • 1 <= transactions.length <= 8
  • transactions[i].length == 3
  • 0 <= a, b < 12
  • a != b
  • 1 <= amount <= 100

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_transfers(transactions: list[list[int]]) -> int:
Java
public int minTransfers(int[][] transactions)

More on the same topics