465. Optimal Account Balancing

Posted on Edited on In

465. Optimal Account Balancing

Description

You are given an array of transactions transactions where transactions[i] = [fromi, toi, amounti] indicates that the person with ID = fromi gave amounti $ to the person with ID = toi.

Return the minimum number of transactions required to settle the debt.

Example 1:

1
2
3
4
5
6
Input: transactions = [[0,1,10],[2,0,5]]
Output: 2
Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.
Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Example 2:

1
2
3
4
5
6
7
8
Input: transactions = [[0,1,10],[1,0,1],[1,2,5],[2,0,5]]
Output: 1
Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.
Therefore, person #1 only need to give person #0 $4, and all debt is settled.

Constraints:

  • 1 <= transactions.length <= 8
  • transactions[i].length == 3
  • 0 <= fromi, toi < 12
  • fromi != toi
  • 1 <= amounti <= 100

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int, int> m;
        for (auto& t : transactions) {
            int from = t[0], to = t[1], amount = t[2];
            m[from] -= amount;
            m[to] += amount;
        }
        vector<int> nums;
        for (auto [_, v] : m) {
            if (v != 0) {
                nums.push_back(v);
            }
        }
        // now we have 2 arraies, the sum of them is the same, the question is:
        //  how many operations are needed to generate one array from the other one
        int res = dfs(0, nums);
        return res;
    }


    int dfs(int idx, vector<int>& nums) {
        int n = nums.size();
        while (idx < n && nums[idx] == 0) {
            idx++;
        }
        if (idx == nums.size()) {
            return 0;
        }
        int res = INT_MAX;
        int cur = nums[idx];
        for (int i = idx + 1; i < nums.size(); i++) {
            if (nums[i] * cur < 0) {
                int previous_num = nums[i];
                nums[i] += cur;
                res = min(res, dfs(idx + 1, nums) + 1);
                nums[i] -= cur;
            }
        }
        return res;
    }
};