6ms ac easy to understand java solution with comments


  • 10
    K
    public int minTransfers(int[][] transactions) {
        if (transactions == null || transactions.length == 0 || transactions[0].length == 0)
            return 0;
        //calculate delta for each account
        Map<Integer, Integer> accountToDelta = new HashMap<Integer, Integer>();
        for (int[] transaction : transactions) {
            int from = transaction[0];
            int to = transaction[1];
            int val = transaction[2];
            if (!accountToDelta.containsKey(from)) {
                accountToDelta.put(from, 0);
            }
            if (!accountToDelta.containsKey(to)) {
                accountToDelta.put(to, 0);
            }
            accountToDelta.put(from, accountToDelta.get(from) - val);
            accountToDelta.put(to, accountToDelta.get(to) + val);
        }
        List<Integer> deltas = new ArrayList<Integer>();
        for (int delta : accountToDelta.values()) {
            if (delta != 0)
                deltas.add(delta);
        }
        //since minTransStartsFrom is slow, we can remove matched deltas to optimize it
        //for example, if account A has balance 5 and account B has balance -5, we know
        //that one transaction from B to A is optimal.
        int matchCount = removeMatchDeltas(deltas);
        //try out all possibilities to get minimum number of transactions
        return matchCount + minTransStartsFrom(deltas, 0);
    }
    
    private int removeMatchDeltas(List<Integer> deltas) {
        Collections.sort(deltas);
        int left = 0;
        int right = deltas.size() - 1;
        int matchCount = 0;
        while (left < right) {
            if (-1 * deltas.get(left) == deltas.get(right)) {
                deltas.remove(left);
                deltas.remove(right - 1);
                right -= 2;
                matchCount++;
            } else if (-1 * deltas.get(left) > deltas.get(right)) {
                left++;
            } else {
                right--;
            }
        }
        return matchCount;
    }
    
    private int minTransStartsFrom(List<Integer> deltas, int start) {
        int result = Integer.MAX_VALUE;
        int n = deltas.size();
        while (start < n && deltas.get(start) == 0)
            start++;
        if (start == n)
            return 0;
        for (int i = start + 1; i < n; i++) {
            if ((long) deltas.get(i) * deltas.get(start) < 0) {
                deltas.set(i, deltas.get(i) + deltas.get(start));
                result = Math.min(result, 1 + minTransStartsFrom(deltas, start + 1));
                deltas.set(i, deltas.get(i) - deltas.get(start));
        }
        }
        return result;
    }

  • 0
    Y

    @KPass use this test case:
    int[][] transactions = new int[][]{{1, 8, 1}, {1, 9, 1}, {2, 8, 10}, {3, 9, 20}, {4, 10, 30}, {5, 11, 40}, {6, 12, 50}, {7, 13, 60}, {20, 80, 10}, {30, 90, 20}, {40, 100, 30}, {50, 110, 40}, {60, 120, 50}, {70, 130, 60}};
    it takes forever to run.


  • 0
    K

    agree, since this solution is O(N!)


  • 0
    K

    @yuhaowang001
    I've done some optimization to pass this test case, however, the overall complexity is unchanged.

    public int minTransfers(int[][] transactions) {
        if (transactions == null || transactions.length == 0 || transactions[0].length == 0)
            return 0;
        Map<Integer, Integer> accountToDelta = new HashMap<Integer, Integer>();
        for (int[] transaction : transactions) {
            int from = transaction[0];
            int to = transaction[1];
            int val = transaction[2];
            if (!accountToDelta.containsKey(from)) {
                accountToDelta.put(from, 0);
            }
            if (!accountToDelta.containsKey(to)) {
                accountToDelta.put(to, 0);
            }
            accountToDelta.put(from, accountToDelta.get(from) - val);
            accountToDelta.put(to, accountToDelta.get(to) + val);
        }
        List<Integer> deltas = new ArrayList<Integer>();
        for (int delta : accountToDelta.values()) {
            if (delta != 0)
                deltas.add(delta);
        }
        int matchCount = removeMatchDeltas(deltas);
        return matchCount + minTransStartsFrom(deltas, 0);
    }
    
    private int removeMatchDeltas(List<Integer> deltas) {
        Collections.sort(deltas);
        int left = 0;
        int right = deltas.size() - 1;
        int matchCount = 0;
        while (left < right) {
            if (-1 * deltas.get(left) == deltas.get(right)) {
                deltas.remove(left);
                deltas.remove(right - 1);
                right -= 2;
                matchCount++;
            } else if (-1 * deltas.get(left) > deltas.get(right)) {
                left++;
            } else {
                right--;
            }
        }
        return matchCount;
    }
    
    private int minTransStartsFrom(List<Integer> deltas, int start) {
        int result = Integer.MAX_VALUE;
        int n = deltas.size();
        while (start < n && deltas.get(start) == 0)
            start++;
        if (start == n)
            return 0;
        for (int i = start + 1; i < n; i++) {
            if ((long) deltas.get(i) * deltas.get(start) < 0) {
                deltas.set(i, deltas.get(i) + deltas.get(start));
                result = Math.min(result, 1 + minTransStartsFrom(deltas, start + 1));
                deltas.set(i, deltas.get(i) - deltas.get(start));
        }
        }
        return result;
    }

  • 0
    P

    Like this solution, but I don't think we should increment matchCount when deltas.get(left) and deltas.get(right) are both 0.


Log in to reply
 

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