C++ O(N) Time with unordered_map


  • 8
    // 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.


  • 1
    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.


  • 1
    R

    @swimmorning Hi there. unordered_map is basically a hash table and it doesn't allow duplicates, so the number (or counts) of elements with a specified key is either 1 or 0. As the link you provided suggests, the average time complexity is surely O(1), or constant. 'Linear in the number of elements counted' amounts to 'linear in 1 or 0'. What do you think? :)


  • 0

    @Rayarrow Yeah, and cppreference.com says it directly.

    Btw, count is not only nicer but maybe also faster (I remember having seen that a while ago).


  • 0

    Ok I just tested it again, adding this before the return:

    for (int i=0; i<100000000; i++)
        //m.count(42);
        m.find(42) != m.end();
    

    I used "Run Code" three times on the small provided custom input. With m.count(42); it took 1516, 1542 and 1529 ms. With m.find(42) != m.end(); it took 1883, 1869 and 1845 ms.


  • 0
    R

    @ManuelP Wow! I also take it as my cheat sheet as its layout seems more comfortable to me.
    Thanks for your "Btw" and tests. So kind of you. I've never delved into the difference of the two methods. As for an unordered_set (or map), I merely took count() and find() as two different ways to express my intention in different scenes. What a waste:(


Log in to reply
 

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