public class Solution {
public int minTransfers(int[][] transactions) {
//I thought it's kind of network flow problem
Map<Integer,Integer> map = new HashMap<>();
for(int[] t : transactions){
map.put(t[1],map.getOrDefault(t[1],0)t[2]);
map.put(t[0],map.getOrDefault(t[0],0)+t[2]);
}
int[] count = new int[1];
helper(map,count);
return count[0];
}
//this getMax() and getMin() function is to get the index(key) of the MaxValue and MinValue
private int getMax(Map<Integer,Integer> map){
int max = 1;
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(max == 1) max = entry.getKey();
else if(entry.getValue() > map.get(max)){
max = entry.getKey();
}
}
return max;
}
private int getMin(Map<Integer,Integer> map){
int min = 1;
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(min == 1) min = entry.getKey();
else if(entry.getValue() < map.get(min)){
min = entry.getKey();
}
}
return min;
}
private void helper(Map<Integer,Integer> map, int[] count){
int max = getMax(map);
int min = getMin(map);
//This means richest one and poorest one are both $0, means balance.
if(map.get(max) == 0 && map.get(min) == 0) return;
//Or we get the min abs value of max and min
int minValue = Math.min(map.get(max),map.get(min));
//let the richest give the poorest the as much as possible money
map.put(max, map.get(max)minValue);
map.put(min, map.get(min)+minValue);
//after done this, add the count
count[0]++;
helper(map,count);
}
}
Java Recursion



@chnsht
If we have the case that persons of (2, 50, 50, ..., 50) need to pay the persons of (51, 50, 50, ..., 50, 51), obviously we could get the minimal number of transactions by letting person "2" pay $1 to both the first and last person of (51, 50, 50, ..., 50, 51) and each person "50" pays one person $50.However, seems your solution doesn't go through this "payment plan". (This example may not be a good one, but you know what I mean.)

@chnsht said in Java Recursion:
For the test case:
{{1, 8, 1}, {1, 13, 21}, {2, 8, 10}, {3, 9, 20}, {4, 10, 61}, {5, 11, 61}, {6, 12, 59}, {7, 13, 60}}Your solution returns 9, however, the correct answer should be 8. There are 8 transactions here and the answer should not be larger than 8.
