pg

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

• We check whether a number a is consecutive by checking whether a-1 or a+1 is in the array.
• We need to record the count of consecutive numbers until the current number.
• We also need to update records, but we only need to update the border of the consecutive numbers.

• How do we get the border? Just use the records of a-1 and a+1.

• So it is a dynamic programming problem,

  • the subproblem is checking whether each number a has a-1 or a+1.
  • the dp structure is a hash table because the array is unsorted and has duplicate numbers.
  • the hash table is used to record the count of consecutive numbers until each distinct number.
  • Because the record is added step by step, so we only need to update the border of the consecutive numbers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int longestConsecutive(vector<int>& nums) {
       unordered_map<int, int> nmap;
       int res = 0;
       for(int i : nums){
           if(nmap.find(i) == nmap.end()){
               int left = (nmap.find(i-1) == nmap.end() ? 0 : nmap[i-1]);
               int right= (nmap.find(i+1) == nmap.end() ? 0 : nmap[i+1]);
               int count = 1 + left + right;
               nmap[i] = count;
               res = max(res, count);

               nmap[i-left] = count;
               nmap[i+right] = count;
           }else
               continue;

       }
       return res;
   }