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.
» Solve this problem
[Thoughts]
Since it requires O(n) solution, normal sort won't be work here. Hash probably is the best choice.
3 Steps:
1. create the hashmap to hold <num, index>
2. scan the num vector from left to right, for each num
i, check whether num -1 is in the map (loop)
ii, check whether num+1 is in the map (loop)
3. track the sequence length during scanning.
[Code]
1: int longestConsecutive(vector<int> &num) {
2: unordered_map<int, int> hashmap;
3: for(int i =0; i< num.size(); i++)
4: {
5: hashmap[num[i]] = i;
6: }
7: vector<int> visited(num.size(), 0);
8: int maxV = INT_MIN;
9: for(int i =0; i< num.size(); i++)
10: {
11: if(visited[i]==1) continue;
12: visited[i]=1;
13: int len = 1;
14: int index = num[i]-1;
15: while(hashmap.find(index) != hashmap.end())
16: {
17: visited[hashmap[index]] =1;
18: index--;
19: len++;
20: }
21: index = num[i]+1;
22: while(hashmap.find(index) != hashmap.end())
23: {
24: visited[hashmap[index]] =1;
25: index++;
26: len++;
27: }
28: if(len > maxV)
29: maxV = len;
30: }
31: return maxV;
32: }
Update 08/23/2014
Interesting discussion in the comments:) I haven't visited my blog for quite long time.
For each num, define D[num] as the longest consecutive sequence from k to num, 0<k<num
So D[num] = D[num-1] +1 if num-1 in the map
=0 if num-1 not in the map
But unfortunately, the unordered_map doesn't keep any order of sequence. It's hard to do the DP via a loop.
Here can use
Memorization to optimize the code. Since for each fresh node, it only visits once. It is O(n) code.
And in the code , the second 'for' loop and the third 'for' loop could be merged together, but here keep them separated for readability.
1: int longestConsecutive(vector<int> &num) {
2: unordered_map<int, int> hashmap;
3: vector<int> length(num.size(),0);
4: for(int i =0; i< num.size(); i++)
5: {
6: hashmap[num[i]]=i;
7: }
8: for(int i =0; i< num.size(); i++)
9: {
10: // skip the node, which already calculate the length
11: if(length[i] > 0) continue;
12: length[i] = consecutiveLength(num[i], hashmap, length);
13: }
14: int maxV = INT_MIN;
15: for(int i =0; i< num.size(); i++)
16: {
17: maxV = length[i]>maxV?length[i]:maxV;
18: }
19: return maxV;
20: }
21: int consecutiveLength(int num, unordered_map<int, int>& hashmap, vector<int>& length)
22: {
23: if(hashmap.find(num) == hashmap.end()) return 0;
24: int index = hashmap[num];
25: // skip the node, which already calculate the length
26: if(length[index] > 0) return length[index];
27: else
28: {
29: // hit each fresh node only once
30: length[index] = consecutiveLength(num - 1, hashmap, length) + 1;
31: return length[index];
32: }
33: }
