465. Optimal Account Balancing

Description

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 thatx ≠ yandz > 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.

Discussion

map<person, debt> + dfs

Copied from leetcode discussion

class Solution {
public:
    int minTransfers(vector<vector<int>>& trans) {
        unordered_map<int, long> bal; // each person's overall balance
        for(auto& t: trans) bal[t[0]] -= t[2], bal[t[1]] += t[2];
        for(auto& p: bal) if(p.second) debt.push_back(p.second);
        return dfs(0, 0);
    }

private:
    int dfs(int s, int cnt) { // min number of transactions to settle starting from debt[s]
        while (s < debt.size() && !debt[s]) ++s; // get next non-zero debt
        int res = INT_MAX;
        for (long i = s+1, prev = 0; i < debt.size(); ++i)
          if (debt[i] != prev && debt[i]*debt[s] < 0) // skip already tested or same sign debt
            debt[i] += debt[s], res = min(res, dfs(s+1,cnt+1)), prev = debt[i]-=debt[s];
        return res < INT_MAX? res : cnt;
    }

    vector<long> debt; // all non-zero balances
};