LeetCode [465] Optimal Account Balancing

465. Optimal Account Balancing

Hard

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. A transaction will be given as a tuple (x, y, z). Note that x ≠ y and z > 0.
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:

Input:
[[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:

Input:
[[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.

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

class Solution { public: int minTransfers(vector<vector<int>>& transactions) { map<int, int> mp;//id, debt for(auto& p:transactions){ mp[p[0]] -= p[2]; mp[p[1]] += p[2]; } vector<int> debts; for(auto& p:mp){ debts.push_back(p.second); } int ret = INT_MAX;//min # transactions dfs(debts, 0, debts.size(), ret, 0); return ret; } //clear up debts[pos] void dfs(vector<int>& debts, int pos, int sz, int& ret, int trans){ if(debts[pos]==0){ if(pos==sz-1) ret = min(ret, trans); else dfs(debts, pos+1, sz, ret, trans);//no transaction needed to clear up debts[pos] } int d = debts[pos]; debts[pos] = 0; for(int i=pos+1; i<sz; ++i){ if(debts[i]*d>=0) continue; if(i>pos+1 && debts[i]==debts[i-1]) continue; debts[i] += d; dfs(debts, pos+1, sz, ret, trans+1); debts[i] -= d; } debts[pos] = d; } };

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

class Solution { public int minTransfers(int[][] transactions) { Map<Integer, Integer> bal = new HashMap<>(); for(int[] t : transactions){ int a = t[0], b = t[1], c = t[2]; bal.put(a, bal.getOrDefault(a, 0)-c); bal.put(b, bal.getOrDefault(b, 0)+c); } return settle(new ArrayList<>(bal.values()), 0); } int settle(List<Integer> list, int start){ while(start<list.size() && list.get(start) == 0) start++; if(start==list.size()) return 0; int r = Integer.MAX_VALUE; for(int i=start+1; i<list.size(); ++i){ if(list.get(start)*list.get(i)<0){ list.set(i, list.get(i)+list.get(start)); r = Math.min(r, 1+settle(list, start+1)); list.set(i, list.get(i)-list.get(start)); } } return r; } }