# Accepted Solution with comments [After the test case correction]

• ``````/*
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()){
}
int result = (pos.size() == 0) ? 0 : trans.length;

for(int i = 0; i < pos.size(); i++){
int first = pos.remove(0);
for(int j = 0; j < neg.size(); j++){
int second = neg.remove(0);
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>();
List<Integer> neg = new ArrayList<Integer>();
/*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;
}
}``````

• 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}}

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

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