Strait forward c++ solution by hash map and 2 pointers with comments


  • 0
    X

    Strait forward c++ solution with comments:

    1. collect the remains for each person

    2. counts the matched (-remain/+remain ) pairs first.
      e.g., one is -4, and other one is 4. there is one transaction

    3. counts the unmatched values by 2 pointer approach
      e.g. -4, 2,2. start is -4 and end is 2, then count the value by increase start and decrease end.
      ...
      int minTransfers(vector<vector<int>>& transactions){
      if (transactions.empty())
      return 0;
      //1) collect the remains for each person
      unordered_map<int, int> remains;
      for (auto transaction : transactions)
      {
      int money = transaction[2];
      remains[transaction[0]] += -money;
      remains[transaction[1]] += money;
      }

      //2) counts the matched (-remain/+remain ) pairs first
      map<int, int> matches;
      int count = 0;
      for (auto remain : remains)
      {
      if (remain.second != 0)
      {
      if (matches.count(-remain.second))
      {
      ++count;
      --matches[-remain.second];
      }
      else
      ++matches[remain.second];
      }
      }

      //3) counts the unmatched values then
      vector<int> res;
      for (auto match : matches)
      {
      while (match.second > 0)
      {
      res.push_back(match.first);
      match.second--;
      }
      }
      if (res.empty())
      return count;

      //now we have a sorted array, let's count the transaction by 2 pointer approach
      int start = 0, end = res.size() - 1;

      int sum = 0;
      while (start < end)
      {
      if (res[start] + res[end] == 0)
      {
      ++count;
      ++start;
      --end;
      }
      else if (res[start] + res[end] > 0)
      {
      ++count;
      ++start;
      res[end] += res[start];
      }
      else
      {
      ++count;
      --end;
      res[start] += res[end];
      }
      }

      return count;
      }

    ...


  • 0

    Your code seems to fail test case [[0,3,9],[1,4,2],[2,5,5],[3,4,6],[4,5,2]] which expected result 4, but your actual output is 5.

    Btw, this problem NPC though.


Log in to reply
 

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