# An amortized O(n) solution?

• Build and tear down the hash table in two passes of the `nums` array

``````class Solution {
public:
int longestConsecutive(vector<int> &nums) {
if (nums.size() == 0) return 0;
unordered_map<int, int> ht;
int range = 1;
for (int i = 0; i < nums.size(); ++i) ht[nums[i]] = 1;
/**
* In amortized analysis, this for-loop with 2 while-loop
* tegother takes O(n) time
*/
for (int i = 0; i < nums.size(); ++i) {
if (ht[nums[i]]) {
int left = nums[i] - 1;
int right = nums[i] + 1;
while (ht[left]) {
/**
* Delete left from hash table so that
* we will not enter "if" statement later
*/
ht[left] = 0;
--left;
}
while (ht[right]) {
ht[right] = 0;
++right;
}
range = MAX(range, right - left - 1);
}
}
return range;
}
};
``````

• @yan35 Actually you can just use `set` or `multiset` to do the same thing where each time just erase the neighbours and then move to the left or right, since set or multiset will always keep the keys inside sorted so it's good enough here.

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