Staff
Optimal Account Balancing
You are given an array transactions where transactions[i] = [from_i, to_i, amount_i] indicates that person from_i gave person to_i amount_i dollars.
After all transactions, each person may have a net balance: they may be owed money, owe money, or be settled. Your task is to determine the minimum number of additional transactions required so that every person's net balance becomes zero.
Return the minimum number of transactions needed to settle all debts.
Example 1
Input
transactions = [[0,1,10],[2,0,5]]Output
2Person 1 must repay 5 dollars to person 0 and 5 dollars to person 2, requiring 2 transactions.
Example 2
Input
transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]Output
1After netting all balances, only person 1 owes person 0 4 dollars, so 1 transaction is enough.
Constraints
- 1 <= transactions.length <= 8
- transactions[i].length == 3
- 0 <= from_i, to_i < 12
- from_i != to_i
- 1 <= amount_i <= 100