FastPrep
Problem · Array

Minimum Account Settlements

Learn this problem
● HardRipplingPHONE SCREEN

Problem statement

Each row of transactions is [from, to, amount], meaning from paid amount on behalf of to.

After all original transactions, people may transfer money among themselves to settle every net balance. A person with a negative balance must pay that amount; a person with a positive balance must receive that amount.

Return the minimum number of settlement transactions required to make every net balance zero.

Interviewer follow-ups

The interviewer first asked for any correct set of transfers that settles all accounts, then asked the candidate to minimize the number of settlement transactions.

Function

minimumSettlements(transactions: String[][]) → int

Examples

Example 1

transactions = [["A","B","10"],["B","C","5"]]return = 2

The net balances are A:+10, B:-5, and C:-5. Both B and C must pay A, so two settlements are necessary.

Example 2

transactions = [["A","B","10"],["B","C","10"]]return = 1

B's incoming and outgoing amounts cancel. One transfer from C to A settles everyone.

Constraints

  • 1 <= transactions.length <= 100
  • amount is a positive integer string.
  • At most 12 people have non-zero final balances.

More Rippling problems

drafts saved locally
public int minimumSettlements(String[][] transactions) {
  // write your code here
}
transactions[["A","B","10"],["B","C","5"]]
expected2
checking account