## 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}.