# C++ O(N) solution with explanation

• Idea is simple. When there is not existing range, the new number will build up a range with length `1` and its lower and upper boundaries are `1`. Now, imagine we have 1 existing range `[i, j] (i <=j)`. For any new number `x`, there are 3 cases:

• `i <= x <= j` : x has no impact to existing range, no action needed
• `x < i-1 || x > j+1`: x has no impact to existing range, but it will set up a new range `[x,x]`
• `x == i-1 || x == j+1`: x extends the existing range. This is what we need to handle.

Based the analysis above, we can use a hash map to store the inserted numbers (key) and range length (value). For each new number, check if it hit the number right outside the range and update accordingly.

``````class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> m;
int res = 0;
for (auto x : nums) {
// already in an existing range, no impact
if (m.count(x)) continue;
int lower = m.count(x-1) ? m[x-1] : 0;
int upper = m.count(x+1) ? m[x+1] : 0;
m[x] = lower + upper + 1;
m[x-lower] = m[x];
m[x+upper] = m[x];
res = max(res, m[x]);
}
return res;
}
};
``````

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