465 Optimal Account Balancing

# 1. Question

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for \$10. Then later Chris gave Alice \$5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y \$z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as`[[0, 1, 10], [2, 0, 5]]`.
Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note:
1. 1.
A transaction will be given as a tuple (x, y, z). Note that`x ≠ y`and`z > 0`.
2. 2.
Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:
1
Input: [[0,1,10], [2,0,5]]
2
3
Output: 2
4
5
Explanation:
6
Person #0 gave person #1 \$10.
7
Person #2 gave person #0 \$5.
8
9
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 \$5 each.
Copied!
Example 2:
1
Input: [[0,1,10], [1,0,1], [1,2,5], [2,0,5]]
2
3
Output: 1
4
5
Explanation:
6
Person #0 gave person #1 \$10.
7
Person #1 gave person #0 \$1.
8
Person #1 gave person #2 \$5.
9
Person #2 gave person #0 \$5.
10
11
Therefore, person #1 only need to give person #0 \$4, and all debt is settled.
Copied!

# 2. Implementation

(1) Hash Table + Backtracking

(1)用hashmap预处理transaction，将balance为0的人去除掉
(2)用backtracking对枚举出所有能将剩余debt settle的组合，
1
class Solution {
2
public int minTransfers(int[][] transactions) {
3
Map<Integer, Long> map = new HashMap<>();
4
5
// Step 1: Preprocessing the transactions, and ingore people with zero debt
6
for (int[] transaction : transactions) {
7
int person1 = transaction;
8
int person2 = transaction;
9
int curDebt = transaction;
10
11
long debt1 = map.getOrDefault(person1, 0L);
12
long debt2 = map.getOrDefault(person2, 0L);
13
14
map.put(person1, debt1 - curDebt);
15
map.put(person2, debt2 + curDebt);
16
}
17
18
List<Long> debts = new ArrayList<>();
19
20
for (long debt : map.values()) {
21
if (debt != 0) {
22
23
}
24
}
25
26
// Step 2： Enumerate all possible combinations to settle the debt
27
int[] res = {Integer.MAX_VALUE};
28
getMinimumTransaction(0, 0, debts, res);
29
return res;
30
}
31
32
public void getMinimumTransaction(int index, int count, List<Long> debts, int[] res) {
33
// Skip settled debt
34
while (index < debts.size() && debts.get(index) == 0) ++index;
35
36
if (index == debts.size()) {
37
res = Math.min(res, count);
38
return;
39
}
40
41
for (int i = index + 1; i < debts.size(); i++) {
42
// Only settle debt when the debts[i] has different sign with debts[index]
43
if (debts.get(i) * debts.get(index) < 0) {
44
debts.set(i, debts.get(i) + debts.get(index));
45
getMinimumTransaction(index + 1, count + 1, debts, res);
46
debts.set(i, debts.get(i) - debts.get(index));
47
}
48
}
49
}
50
}
Copied!
(2) HashMap + Two Pointers + Backtracking

1
class Solution {
2
public int minTransfers(int[][] transactions) {
3
Map<Integer, Long> map = new HashMap<>();
4
5
// Step 1: Preprocessing the transactions, and ingore people with zero debt
6
for (int[] transaction : transactions) {
7
int person1 = transaction;
8
int person2 = transaction;
9
int curDebt = transaction;
10
11
long debt1 = map.getOrDefault(person1, 0L);
12
long debt2 = map.getOrDefault(person2, 0L);
13
14
map.put(person1, debt1 - curDebt);
15
map.put(person2, debt2 + curDebt);
16
}
17
18
List<Long> debts = new ArrayList<>();
19
20
for (long debt : map.values()) {
21
if (debt != 0) {
22
23
}
24
}
25
26
// Step 2: use two pointers to cancel out debts that match with each other
27
Collections.sort(debts);
28
29
int start = 0, end = debts.size() - 1;
30
int matchCount = 0;
31
while (start < end) {
32
if (debts.get(start) + debts.get(end) == 0) {
33
debts.remove(start);
34
//due to start has been removed: right-1 is correct index
35
debts.remove(end - 1);
36
// adjust end with end - 2 since two elements have been removed
37
end -= 2;
38
++matchCount;
39
}
40
else if (debts.get(start) + debts.get(end) < 0) {
41
++start;
42
}
43
else {
44
--end;
45
}
46
}
47
48
// Step 3： Enumerate all possible combinations to settle the debt
49
int[] res = {Integer.MAX_VALUE};
50
getMinimumTransaction(0, 0, debts, res);
51
return matchCount + res;
52
}
53
54
public void getMinimumTransaction(int index, int count, List<Long> debts, int[] res) {
55
// Skip settled debt
56
while (index < debts.size() && debts.get(index) == 0) ++index;
57
58
if (index == debts.size()) {
59
res = Math.min(res, count);
60
return;
61
}
62
63
for (int i = index + 1; i < debts.size(); i++) {
64
// Only settle debt when the debts[i] has different sign with debts[index]
65
if (debts.get(i) * debts.get(index) < 0) {
66
debts.set(i, debts.get(i) + debts.get(index));
67
getMinimumTransaction(index + 1, count + 1, debts, res);
68
debts.set(i, debts.get(i) - debts.get(index));
69
}
70
}
71
}
72
}
Copied!

# 3. Time & Space Complexity

(1) Hash Table + Backtracking: 时间复杂度O(n!), n是debt不为0的个数，空间复杂度O(m + n), m是人的个数
(2) HashMap + Two Pointers + Backtracking：时间复杂度O(n!), 空间复杂度O(m + n)