C++ O(N) Time with unordered_map


  • 7
    // OJ: https://leetcode.com/problems/k-diff-pairs-in-an-array
    // Author: github.com/lzl124631x
    // Time: O(N)
    // Space: O(N)
    class Solution {
    public:
      int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        unordered_map<int, int> m;
        for (int n : nums) m[n]++;
        int cnt = 0;
        for (auto p : m) {
          if ((!k && p.second > 1)
            || (k && m.count(p.first + k))) ++cnt;
        }
        return cnt;
      }
    };
    

  • 0
    D

    Nice solution!


  • 0
    A

    @lzl124631x This solution is really great! Thanks!


  • 0
    F

    Nice idea. Thanks.


  • 0
    S

    Hi @lzl124631x
    First of all thanks for the nice solution, however, I think the following code is O(N^2) rather than O(N), since count() in unordered_map is O(N). (http://www.cplusplus.com/reference/unordered_map/unordered_map/count/)

    for (auto p : m) {
        if ((!k && p.second > 1)
            || (k && m.count(p.first + k))) ++cnt;
        }
    takes 32ms
    

    Instead of counting the number of key in the map, you can use find() which is O(1) for unordered_map.

    for (auto p : m) {
         if ((!k && p.second > 1)
         || (k && m.find(p.first + k) != m.end())) ++cnt;
    }
    takes 29ms
    

    Thanks.


Log in to reply
 

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