# C++ O(N) solution walking the longest streak - Accepted

• In a first sweep, we store all the elements in an unordered map that maps the element to it's chain length. We use a second map to keep track of the elements of the sequence we already visited.

In a second sweep, we start walking successors by checking if the successor is in the map. While we are walking the sequence, we increment the length and mark the successor as visited. If we encounter a successor we have already visited, we can simply take over it's chain length.

This is O(N) because we walk each element in the map exactly once (That's why we keep the visited map). The idea is similar to a graph traversal where successors are edges.

For a better explanation look at Stefan Pochmann's solution here.

``````class Solution {
public:
int longestConsecutive(vector<int>& nums) {
// records the length starting at nums[i]
unordered_map<int, int>  chainLength;
// tracks if we already visited nums[i] in our sweep
unordered_map<int, bool> visited;

// fill in the maps
for (int i=0; i<nums.size(); ++i) {
chainLength[nums[i]] = 1;
visited[nums[i]] = false;
}

// follow the successor to form a chain
int maxLen = 0;
for (int i=0; i<nums.size(); ++i) {

// we already visited this element
if (visited[nums[i]]) { continue; }

// follow the chain of this element
int next = nums[i] + 1;
int len  = 0;
while (visited.count(next)) {
if (visited[next]) {
len += chainLength[next];
break;
}
else {
++len;
visited[next] = true;
}
++next;
}

// record the chain length and mark visited
chainLength[nums[i]] += len;
visited[nums[i]] = true;

// check if we improve the chain length
maxLen = max(maxLen, chainLength[nums[i]]);
}

return maxLen;
}
};
``````

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