6-liner O(N) with hash map for frequency (with explanation)

  • 0

    If we convert the original array nums[] to a frequency map unordered_map<int,int> frq: value -> count, the algorithm will be straight forward since the frequency map counts the duplicates of each unique value:

    • if k < 0, res = 0 since the absolute difference is invalid;
    • if k == 0, res is simple how many keys in frq mapping to value > 1;
    • if k > 0, each k-diff pair can be uniquely written as (x, x+k), where both x and x+k need to be keys in map frq.
        int findPairs(vector<int>& nums, int k) {
          if (k < 0) return 0; // invalid abs diff
          unordered_map<int,int> frq; // frequency for each unique number
          for (int n:nums) ++frq[n];
          int res = 0;
          for (auto& p:frq) res += k*frq.count(p.first+k) || !k && p.second>1;
          return res;

Log in to reply

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