source: https://leetcode.com/problems/optimal-account-balancing/
Table of Contents
Optimal Account Balancing
Description
You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.
Return the minimum number of transactions required to settle the debt.
Example 1:
Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
- Person #0 gave person #1 $10.
- Person #2 gave person #0 $5.
- Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.
Example 2:
Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
- Person #0 gave person #1 $10.
- Person #1 gave person #0 $1.
- Person #1 gave person #2 $5.
- Person #2 gave person #0 $5.
- Therefore, person #1 only need to give person #0 $4, and all debt is settled.
Constraints:
- 1 <= transactions.length <= 8
- transactions[i].length == 3
- 0 <= fromi, toi < 12
- fromi != toi
- 1 <= amounti <= 100
Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class Solution { public int minTransfers(int[][] transactions) { int[] bal = new int[12]; for(int[] transaction: transactions){ bal[transaction[0]] = bal[transaction[0]] - transaction[2]; bal[transaction[1]] = bal[transaction[1]] + transaction[2]; } int min = Integer.MAX_VALUE; for(int i=0;i<bal.length;i++){ if(bal[i]>0){ min = Math.min(min, settle(bal, i)); } } return min==Integer.MAX_VALUE?0:min; } private int settle(int[] bal, int idx){ if(idx<0) return 0; int min = Integer.MAX_VALUE; int count = 0; if(idx>=0){ for(int i=0;i<bal.length;i++){ if(i!=idx && bal[i]<0){ int sum = bal[idx] + bal[i]; int temp1 = bal[i]; int temp2 = bal[idx]; bal[i] = sum>=0 ?0:sum; bal[idx] = sum<0 ?0:sum; min = Math.min(min, 1+settle(bal, getPositiveBalanceIndex(bal))); bal[i] = temp1; bal[idx] = temp2; } } } return min; } private int getPositiveBalanceIndex(int[] bal){ for(int i=0;i<bal.length;i++){ if(bal[i]>0){ return i; } } return -1; } } |