Accepted Solution with comments [After the test case correction]


  • 2
    /*
    This is a straight forward brutal force problem.
    We first replay all the transactions while keeping a balance for each people
    Then we try to settle the money asap.
    
    How do we settle?
    We group the balances into 2 arrays, pos and neg
    We use a nested for loop to try all the possible sequence of settlement.
    
    
    */
    public class Solution {
        public int minTransfers(int[][] trans) {
            Map<Integer, Integer> net = new HashMap<>();
            for(int i = 0; i < trans.length; i++){
                net.put(trans[i][0], net.getOrDefault(trans[i][0], 0) - trans[i][2]);
                net.put(trans[i][1], net.getOrDefault(trans[i][1], 0) + trans[i][2]);
            }
            int res = 0;
            List<Integer> pos = new ArrayList<Integer>();
            List<Integer> neg = new ArrayList<Integer>();
            
            for(int i : net.values()){
                if(i > 0) pos.add(i);
                if(i < 0) neg.add(i);
            }
            int result = (pos.size() == 0) ? 0 : trans.length;
            
            for(int i = 0; i < pos.size(); i++){
                int first = pos.remove(0);
                pos.add(first);
                for(int j = 0; j < neg.size(); j++){
                    int second = neg.remove(0);
                    neg.add(second);
                    result =Math.min(collapse(pos, neg), result);
    
                }
            }
            return result;
        }
        
        private int collapse(List<Integer> positive, List<Integer> negative){
            int count = 0;
            List<Integer> pos = new ArrayList<Integer>();
            pos.addAll(positive);
            List<Integer> neg = new ArrayList<Integer>();
            neg.addAll(negative);
            /*Optionally remove either one or both of the front element in 2 lists*/    
            while(pos.size() != 0 && neg.size() != 0){
                if(pos.get(0) < Math.abs(neg.get(0))){
                    neg.set(0, neg.get(0) + pos.get(0));
                    pos.remove(0);
                }else if (pos.get(0) > Math.abs(neg.get(0))){
                    pos.set(0, pos.get(0) + neg.get(0));
                    neg.remove(0);
                }else{
                    pos.remove(0);
                    neg.remove(0);
                }
                count++;
            }
            return count;
        }
    }

  • 0
    F

    Interesting, and I test your code using the test case in the 3rd post.

    The C++ version in another post returns 15. While yours return 18. Only one can be right.

    {{6,29,18},{1,22,84},{4,25,16},{7,22,16},{5,27,79},{7,27,60},{3,28,95},{4,20,95},{7,25,99},{1,29,25},{9,21,87},{4,26,39},{5,23,67},{6,22,68},{3,29,94},{8,24,66},{6,28,33},{9,28,85},{8,28,28},{3,21,25},{7,26,3},{3,22,89},{6,28,58},{6,28,45},{1,29,3},{7,21,95},{0,25,14},{8,27,37},{5,21,98},{9,23,57},{8,24,21},{8,25,78},{2,23,15},{3,24,50},{1,26,66},{6,21,38},{6,28,30},{8,29,49},{3,20,86},{4,22,91},{1,21,18},{1,26,22},{5,25,75},{5,28,48},{2,26,83},{3,28,3},{2,27,76},{7,22,73},{8,27,97},{2,26,49},{0,20,83},{7,23,47},{9,29,94},{2,27,43},{5,25,50},{7,29,76},{1,20,26},{9,28,77},{1,29,63},{9,26,55},{1,25,17},{3,28,37}}


  • 0

    good idea
    but I think the way to go thru all possible permutation of pos and neg list is not complete.
    There are n! kinds of permutation, while u only check n of them.


Log in to reply
 

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