Java solution


  • 1
    B

    Based on the popular solution and improved it a little bit.
    https://discuss.leetcode.com/topic/76158/11-liner-9ms-dfs-solution-detailed-explanation/9

    public class Solution {
        public int minTransfers(int[][] transactions) {
            Map<Integer, Long> map = new HashMap();
            for(int[] t: transactions){
                long val1 = map.getOrDefault(t[0], 0L);
                long val2 = map.getOrDefault(t[1], 0L);
                map.put(t[0], val1 - t[2]);
                map.put(t[1], val2 + t[2]);
            }        
            
            List<Long> list = new ArrayList();
            for(long val: map.values()){
                if(val != 0) list.add(val);
            }
            
            Long[] debts = new Long[list.size()];
            debts = list.toArray(debts);
            return helper(debts, 0 , 0);
        }
            
        int helper(Long[] debts, int pos, int count){
            while(pos < debts.length && debts[pos] == 0) pos++;
            if (pos >= debts.length) {
                return count;
            }
            int res = Integer.MAX_VALUE;
            for(int i = pos + 1; i < debts.length; i++){
                if(debts[pos] * debts[i] < 0){
                  debts[i] += debts[pos];
                  res = Math.min(res, helper(debts, pos + 1, count + 1));
                  debts[i] = debts[i] - debts[pos];
                }
            }
            return res;
        }
    
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.