FastPrep
Problem · Array

Optimal Account Balancing

Learn this problem
● HardPinterest logoPinterestFULLTIMEONSITE INTERVIEW

Problem statement

You are given a list transactions. Each transaction [from, to, amount] means that person from paid amount on behalf of person to.

After all transactions, people may transfer money directly between one another to settle every net balance. One settlement transfer may use any positive amount between any two people.

Return the minimum number of settlement transfers needed so that every person's net balance becomes zero.

Function

minTransfers(transactions: int[][]) → int

Examples

Example 1

transactions = [[0,1,10],[2,0,5]]return = 2

The net balances are -5 for person 0, +10 for person 1, and -5 for person 2. Two transfers are necessary and sufficient.

Example 2

transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]return = 1

After combining all activity, only two nonzero net balances remain, with equal magnitude and opposite signs. One transfer settles them.

Constraints

  • 1 <= transactions.length <= 8
  • Each transaction contains exactly three integers [from, to, amount].
  • 0 <= from, to <= 20
  • from != to
  • 1 <= amount <= 100

More Pinterest problems

drafts saved locally
public int minTransfers(int[][] transactions) {
    // Write your code here.
}
transactions[[0,1,10],[2,0,5]]
expected2
checking account