# Is it possible to solve this problem in REAL O(n) complexity? Without HashMap.

• Has any one an idea how to solve this problem without using HashMap? I don't think that when using map.find() or map.contains() inside for-next solution complexity still remains O(n).

Please, correct me if i'm wrong.

• To answer the second part of your question, if your solution inserts and erases each element from the hashMap exactly once, it is O(n).

• i use radix sort to do O(n). although it takes more memory than solution using hashmap, it also use O(n) memory.

``````class Solution {
public:
int longestConsecutive(vector<int> &num) {
for (int it = 0; it < num.size(); ++it) {
}
int pow10 = 1;
for (int i = 1; i < 11; ++i) {
pow10 *= 10;
for (int j = 0; j < 19; ++j) {
}
}
}
vector<int> ans;
for (int j = 0; j < 19; ++j) {
ans.push_back(*it);
}
}
int cons = 0, longest = 0;;
int prev = 0;
for (int it = 0; it < ans.size(); ++it) {
printf("%d ", ans[it]);
if (cons) {
if (ans[it-1]+1 == ans[it]) {
cons++;
prev = ans[it];
}
else if (ans[it-1] != ans[it]) {
cons = 0;
}
}
if (cons == 0) {
cons = 1;
prev = ans[it];
}
longest = max(longest, cons);
}
longest = max(longest, cons);
return longest;
}
};``````

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