## Saturday, February 23, 2013

### [LeetCode] Longest Consecutive Sequence, Solution

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:       }
``````