Share my straightforward C++ solution, 6ms


  • 1
    I
    class Solution {
    public:
        int minTransfers(vector<vector<int>>& transactions) {
            unordered_map<int, int> mp;
            for (auto x : transactions) {
                mp[x[0]] -= x[2];
                mp[x[1]] += x[2];
            }
            vector<int> in;
            vector<int> out;
            for (auto x : mp) {
                if (x.second < 0) out.push_back(-x.second);
                else if (x.second > 0) in.push_back(x.second);
            }
            int amount = 0;
            for (auto x : in) amount += x;
            if (amount == 0) return 0;
            int res = (int)in.size() + (int)out.size() - 1;
            dfs(in, out, 0, 0, amount, 0, res);
            return res;
        }
        
        void dfs(vector<int> &in, vector<int> &out, int i, int k, 
                 int amount, int step, int &res) {
            if (step >= res) return;
            if (amount == 0) {
                res = step;
                return;
            }
            if (in[i] == 0) {
                ++i;
                k = 0;
            }
            for (int j = k; j < out.size(); j++) {
                int dec = min(in[i], out[j]);
                if (dec == 0) continue;
                in[i] -= dec;
                out[j] -= dec;
                dfs(in, out, i, j + 1, amount - dec, step + 1, res);
                in[i] += dec;
                out[j] += dec;
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.