leetCode longest consecutive sequence

leetCode longest consecutive sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

 

int longestConsecutive(vector<int> &num) {
unordered_set<int> temp; //O(1) time to insert , find and delete
int max1=1;
for(int i=0 ; i< num.size();i++)
temp.insert(num[i]);
for(int i=0 ; i< num.size();i++)
{
int count=1;
int left= num[i]-1;
int right= num[i]+1;
while(temp.find(left) != temp.end())
{
count++;
temp.erase(left);
left -= 1;
}
while(temp.find(right) != temp.end())
{
count++;
temp.erase(right);
right += 1;
}
max1=(count > max1)?count:max1;
if(temp.empty())
break;
}
return max1;
}
]
After an element is checked, it should be removed from the set. Otherwise, time complexity would be O(mn) in which m is the average length of all consecutive sequences.

If n is number of elements, m is average length of consecutive sequence, and m==n, then the time complexity is O(n^2). The reason is that in this case, no element is removed from the set each time. Use this array to understand above point: {1,3,5,7,9}.