# 6ms ac easy to understand java solution with comments

• ``````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)
}
//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;
}``````

• @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.

• agree, since this solution is O(N!)

• @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)
}
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;
}``````

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

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