Description
You are given an array of transactions where transactions[i] = [from_i, to_i, amount_i]. Return the minimum number of transactions required to settle the debt.
Examples
Input:
transactions = [[0,1,10],[2,0,5]]Output:
2Explanation:
Person 0 pays 5 to person 1, person 2 pays 5 to person 1.
Input:
transactions = [[1]]Output:
1Explanation:
Minimal case with a single-element matrix.
Input:
transactions = [[0,1,10],[1,2,5],[2,0,8]]Output:
2Explanation:
Person 0 owes 2 net (paid 10 to person 1, received 8 from person 2). Person 1 owes 5 net (received 10 from person 0, paid 5 to person 2). Person 2 owes -3 net (received 5 from person 1, paid 8 to person 0). To settle: person 0 pays 2 to person 2, and person 1 pays 3 to person 2. This requires 2 transactions.
Constraints
- •
1 ≤ transactions.length ≤ 8 - •
0 ≤ from_i, to_i ≤ 20