Google
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 thatx ≠ yandz > 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[0];
8
int person2 = transaction[1];
9
int curDebt = transaction[2];
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
debts.add(debt);
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[0];
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[0] = Math.min(res[0], 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
思路: 这里和上面解法唯一的不同的是在第二步里,我们进行进一步的预处理,用two pointers的方法去除掉可以直接match的debt
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[0];
8
int person2 = transaction[1];
9
int curDebt = transaction[2];
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
debts.add(debt);
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[0];
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[0] = Math.min(res[0], 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)