# My Accepted O(n) C++ code with one unordered_map (explained)

• (1)The values are added to an unordered_map.

(2) Scan the unordered_map for consecutive values. Here I use a boolean flag (stored in the unordered map) to note whether that value is already scanned/visited. At each value (that is not already visited), search for decreasing sequence (ie. the presence of value - 1, value -2, etc in the unordered map). Then search for the increasing sequence. Increase the length accordingly.

The use of visited flag makes sure that unordered_map scan is O(n) (any value will be visited twice at most 1. in scanning the map, 2. in finding a sequence)

Let me know if you have any question.

Thanks.

``````int longestConsecutive(vector<int> &num) {
unordered_map<int, bool> um;
typedef pair<int,bool> umpair;
for (int i = 0; i < num.size(); i++)
um.insert(umpair(num[i], false));

int maxLen = 0;
for (auto start = um.begin(); start != um.end(); start++)
{
if (start->second == true)
continue;
int len = 1;
auto cur = start;
cur->second = true;

//find decreasing values seq from current value
while (um.find(cur->first -1) != um.end())
{
cur = um.find(cur->first - 1);
len++;
cur->second = true;
}

//find increasing values seq from current value
cur = start;
while (um.find(cur->first + 1) != um.end())
{
cur = um.find(cur->first + 1);
len++;
cur->second = true;
}
if (len > maxLen)
maxLen = len;
}
return maxLen;
``````

}

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