# C++ O(N) Time with unordered_map

• ``````// 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;
}
};
``````

• Nice solution!

• @lzl124631x This solution is really great! Thanks!

• Nice idea. Thanks.

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

• @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? :)

• @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).

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

• @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:(

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