LeetCode 128 - Longest Consecutive Sequence

Jiaxin's LeetCode: Longest Consecutive Sequence @LeetCode

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.

http://blog.csdn.net/itismelzp/article/details/51636555
使用一个Map保存连续序列两个边缘的值，这个值表示这个序列最大宽度。

如有nums = [1,2,3,4,5]，则map.get(1) = map.get(5) = 5;

设有nums = [1,2,5,6,3,4].

    1 2 3 4 5 6

1: 1

2: 2 2

5: 2 2       1

6: 2 2       2 2

3: 3 2 3    2 2

4: 6 2 3 6 2 6

https://discuss.leetcode.com/topic/6148/my-really-simple-java-o-n-solution-accepted

We will use HashMap. The key thing is to keep track of the sequence length and store that in the boundary points of the sequence. For example, as a result, for sequence {1, 2, 3, 4, 5}, map.get(1) and map.get(5) should both return 5.

Whenever a new element n is inserted into the map, do two things:

1. See if n - 1 and n + 1 exist in the map, and if so, it means there is an existing sequence next to n. Variables left and right will be the length of those two sequences, while 0 means there is no sequence and n will be the boundary point later. Store (left + right + 1) as the associated value to key n into the map.
2. Use left and right to locate the other end of the sequences to the left and right of n respectively, and replace the value with the new length.

Everything inside the for loop is O(1) so the total time is O(n). 

public int longestConsecutive(int[] num) {
    int res = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int n : num) {
        if (!map.containsKey(n)) {
            int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
            int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
            // sum: length of the sequence n is in
            int sum = left + right + 1;
            map.put(n, sum);
            
            // keep track of the max length 
            res = Math.max(res, sum);
            
            // extend the length to the boundary(s)
            // of the sequence
            // will do nothing if n has no neighbors
            map.put(n - left, sum);
            map.put(n + right, sum);
        }
        else {
            // duplicates
            continue;
        }
    }
    return res;
}

Another ways is Sort and find longest increasing sequence. O(nlog(n)) Time. O(1) Space

	* Solution: HashMap Space O(n) Time Complexity O(n) -- 限制O(n), 排序是O(nlog(n)) ---> 必定是空间换时间 * {100, 2, 3, 200, 1, 4}, For a give number 2
	* first search increasing consecutive(right side), 3,4
	* then search descending consecutive(left side), 1.
	* Every node in the sequence has been visited, next time it will be skipped.
	* At most, we will visit n node. --> O(n)
	*
	* Another ways is Sort and find longest increasing sequence. O(nlog(n)) Time. O(1) Space

http://rainykat.blogspot.com/2017/01/leetcodefg-128-longest-consecutive.html

Use HashMap to store val and its current length of consecutive elements(not necessarily final),

only updating and maintain max length on boundary points(n-left & n+right). 

Complexity: O(N)

    public int longestConsecutive(int[] num) {
        int len = 0;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();//<val,len>
        for(int n:num){
            if(!map.containsKey(n)){
                //1.check if n has conseq and update len
                int left = (map.containsKey(n-1))?map.get(n-1):0;
                int right = (map.containsKey(n+1))?map.get(n+1):0;
                int sum = left + right +1;
                map.put(n,sum);
                len = Math.max(sum,len);
                // 2.Union by only updating boundary(maintaining total len)
                // Leave middle k-v dirty to avoid cascading update
                map.put(n-left,sum);
                map.put(n+right,sum);
            }else{
                //duplicates
                continue;
            }
        }
        return len;
    }

https://discuss.leetcode.com/topic/9088/o-n-hashmap-java-solution

Use a hashmap to map a number to its longest consecutive sequence length, each time find a new consecutive sequence, only the begin number and end number need to be modified.

The code is right, but just difficult to explain and understand it's correctness. for example what Map<Integer, Integer> map stores, what's the key and value.

100, 5, 4, 200, 2, 3, 1
Map:
{100=1}
{100=1, 5=1}
{100=1, 4=2, 5=2}
{100=1, 4=2, 5=2, 200=1}
{2=1, 100=1, 4=2, 5=2, 200=1}
{2=4, 3=1, 100=1, 4=2, 5=4, 200=1}
{1=5, 2=4, 3=1, 100=1, 4=2, 5=5, 200=1}

    public int longestConsecutive(int[] num) {
        int longest = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0;i < num.length;i++){
            // if there is no duplicates, these two lines can be commented
            if(map.containsKey(num[i])) continue;
            map.put(num[i],1);
            
            int end = num[i];
            int begin = num[i];
            if(map.containsKey(num[i]+1))
                end = num[i] + map.get(num[i]+1);
            if(map.containsKey(num[i]-1))
                begin = num[i] - map.get(num[i]-1);
            longest = Math.max(longest, end-begin+1);
            map.put(end, end-begin+1);
            map.put(begin, end-begin+1);
        }
        return longest;
    }

X.
http://www.cnblogs.com/grandyang/p/4276225.html

    public int longestConsecutive(int[] nums) {
        int res = 0;
        Set<Integer> s = new HashSet<Integer>();
        for (int num : nums) s.add(num);
        for (int num : nums) {
            if (s.remove(num)) {
                int pre = num - 1, next = num + 1;
                while (s.remove(pre)) --pre;
                while (s.remove(next)) ++next;
                res = Math.max(res, next - pre - 1);
            }
        }
        return res;
    }

https://discuss.leetcode.com/topic/25493/simple-fast-java-solution-using-set
https://discuss.leetcode.com/topic/17980/another-accepted-java-o-n-solution/2

public int longestConsecutive(int[] num) {
  int max = 0;
  
  Set<Integer> set = new HashSet<Integer>();
  for (int i = 0; i < nums.length; i++) {
    set.add(nums[i]);
  }
  
  for (int i = 0; i < nums.length; i++) {
    int count = 1;
    
    // look left
    int num = nums[i];
    while (set.contains(--num)) {
      count++;
      set.remove(num);
    }
    
    // look right
    num = nums[i];
    while (set.contains(++num)) {
      count++;
      set.remove(num);
    }
    
    max = Math.max(max, count);
  }
  
  return max;
}

- This doesn't work for stream, as it first read all data

Using a set to collect all elements that hasn't been visited. search element will be O(1) and eliminates visiting element again.

public int longestConsecutive(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    
    Set<Integer> set = new HashSet<Integer>();
    
    for(int num: nums) set.add(num);//\\
    int max = 1;
    for(int num: nums) {
        if(set.remove(num)) {//num hasn't been visited
            int val = num;
            int sum = 1;
            while(set.remove(val-1)) val--;
            sum += num - val;
            
            val = num;
            while(set.remove(val+1)) val++;
            sum += val - num;
            
            max = Math.max(max, sum);
        }
    }
    return max;
}

https://discuss.leetcode.com/topic/6148/my-really-simple-java-o-n-solution-accepted
We will use HashMap. The key thing is to keep track of the sequence length and store that in the boundary points of the sequence. For example, as a result, for sequence {1, 2, 3, 4, 5}, map.get(1) and map.get(5) should both return 5.

Whenever a new element n is inserted into the map, do two things:

1. See if n - 1 and n + 1 exist in the map, and if so, it means there is an existing sequence next to n. Variables left and right will be the length of those two sequences, while 0 means there is no sequence and n will be the boundary point later. Store (left + right + 1) as the associated value to key n into the map.
2. Use left and right to locate the other end of the sequences to the left and right of n respectively, and replace the value with the new length.

Everything inside the for loop is O(1) so the total time is O(n). Please comment if you see something wrong. Thanks.

public int longestConsecutive(int[] num) {
    int res = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int n : num) {
        if (!map.containsKey(n)) {
            int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
            int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
            // sum: length of the sequence n is in
            int sum = left + right + 1;
            map.put(n, sum);
            
            // keep track of the max length 
            res = Math.max(res, sum);
            
            // extend the length to the boundary(s)
            // of the sequence
            // will do nothing if n has no neighbors
            map.put(n - left, sum);
            map.put(n + right, sum);
        }
        else {
            // duplicates
            continue;
        }
    }
    return res;
}

X. Use Hashset
https://leetcode.com/articles/longest-consecutive-sequence/

• Time complexity : $O(n)$.
  Although the time complexity appears to be quadratic due to the while loop nested within the forloop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for $n$ iterations throughout the entire runtime of the algorithm. This means that despite looking like $O(n \cdot n)$ complexity, the nested loops actually run in $O(n + n) = O(n)$time. All other computations occur in constant time, so the overall runtime is linear.

  public int longestConsecutive(int[] nums) {

    Set<Integer> num_set = new HashSet<Integer>();

    for (int num : nums) {

      num_set.add(num);

    }

    int longestStreak = 0;

    for (int num : num_set) {

      if (!num_set.contains(num - 1)) {

        int currentNum = num;

        int currentStreak = 1;

        while (num_set.contains(currentNum + 1)) {

          currentNum += 1;

          currentStreak += 1;

        }

        longestStreak = Math.max(longestStreak, currentStreak);

      }

    }

    return longestStreak;

  }

https://discuss.leetcode.com/topic/15383/simple-o-n-with-explanation-just-walk-each-streak

First turn the input into a set of numbers. That takes O(n) and then we can ask in O(1) whether we have a certain number.

Then go through the numbers. If the number n is the start of a streak (i.e., n-1 is not in the set), then test m = n+1, n+2, n+3, ... and stop at the first number m not in the set. The length of the streak is then simply m-n and we update our global best with that. Since we check each streak only once, this is overall O(n). This ran in 44 ms on the OJ, one of the fastest Python submissions.

   public int longestConsecutive(int[] nums) {
            Set<Integer> set = new HashSet<>();
            for(int n : nums) {
                set.add(n);
            }
            int best = 0;
            for(int n : set) {
                if(!set.contains(n - 1)) {  // only check for one direction
                    int m = n + 1;
                    while(set.contains(m)) {
                        m++;
                    }
                    best = Math.max(best, m - n);
                }
            }
            return best;
        }

http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/

public static int longestConsecutive(int[] num) {
 // if array is empty, return 0
 if (num.length == 0) {
  return 0;
 }
 
 Set<Integer> set = new HashSet<Integer>();
 int max = 1;
 
 for (int e : num)
  set.add(e);
 
 for (int e : num) {
  int left = e - 1;
  int right = e + 1;
  int count = 1;
 
  while (set.contains(left)) {
   count++;
   set.remove(left);
   left--;
  }
 
  while (set.contains(right)) {
   count++;
   set.remove(right);
   right++;
  }
 
  max = Math.max(count, max);
 }
 
 return max;
}

X. Best http://www.keithschwarz.com/interesting/code/?dir=longest-range
    public static int longestRange(int[] arr) {
        /* Begin by creating a hash table that holds all of the array
         * elements.
         */
        Set<Integer> values = new HashSet<Integer>();
        for (int value: arr)
            values.add(value);
        
        /* Keep track of the longest range we've seen so far.  Initially,
         * this is the empty range.
         */
        int longest = 0;
        
        /* Scan across the array, searching for the longest range of values
         * contained in that array.
         */
        for (int value: arr) {
            /* To avoid unnecessary work, don't process this element if
             * we already did.  To mark that it has been processed, we
             * remove the element.  Since Java's Set#remove function
             * returns whether the element was removed successfully, we
             * can combine the test/remove operation into one.
             */
            if (!values.remove(value)) continue;
            
            /* Track how many total elements are in the range containing
             * the current element.  Initially this is one, because the
             * range contains this element.
             */
            int rangeLength = 1;
            
            /* See how many elements are greater than the current value
             * and contained in the range.  To avoid integer overflow,
             * at each step we track whether the element we're about to
             * probe is greater than the current element; on an overflow,
             * this will be false.
             */
            for (int i = 1; value + i > value; ++i) {
                /* Again, combine the test/remove operation into
                 * one.
                 */
                if (!values.remove(value + i)) break;
                
                ++rangeLength;
            }
            
            /* Using similar logic, see how many elements in the range
             * are smaller than the current value.
             */
            for (int i = 1; value - i < value; ++i) {
                if (!values.remove(value - i)) break;
                ++rangeLength;
            }
            
            /* Update the length of the longest range we've seen so far. */
            if (longest < rangeLength) longest = rangeLength;
        }
        
        /* Hand back the length of the longest range we encountered. */
        return longest;
    }

 private int findConsecutive(HashSet<Integer> set, int num, int step) {  
   int len = 0;  
   while (set.contains(num)) {  
     ++len;  
     set.remove(num);  
     num += step;  
   }  
   return len;  
 }  
   
 public int longestConsecutive(int[] nums) {  
   HashSet<Integer> set = new HashSet<Integer>();  
   // find all   
   for (int num : nums) {  
     set.add(num);  
   }  
   // find longest seq  
   int maxLen = 0;  
   for (int num : nums) {  
     if (set.contains(num)) {  
       set.remove(num); 
       int len = 1 + findConsecutive(set, num-1, -1);  
       len += findConsecutive(set, num+1, 1);  
       maxLen = Math.max(maxLen, len);  
     }  
   }  
   return maxLen;  
 }  

 private int findConsecutive(HashMap<Integer, Boolean> map, int num, int step) {  
   int len = 0;  
   while (map.containsKey(num)) {  
     ++len;  
     map.put(num, true);  
     num += step;  
   }  
   return len;  
 }  
   
 public int longestConsecutive(int[] nums) {  
   HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();  
   // find all   
   for (int num : nums) {  
     map.put(num, false);  
   }  
   // find longest seq  
   int maxLen = 0;  
   for (int num : nums) {  
     if (!map.get(num)) {  
       map.put(num, true);  
       int len = 1 + findConsecutive(map, num-1, -1);  
       len += findConsecutive(map, num+1, 1);  
       maxLen = Math.max(maxLen, len);  
     }  
   }  
   return maxLen;  
 }  

/* Per definition of the map,  
  * - l maps to the len of a left range where l itself is the rightmost element;  
  * - r maps to the len of a right range where r is the leftmost element.  
  * After merging left and right ranges into one,  
  * - the original leftmost of left range becomes the new leftmost;  
  * - the original rightmost of right range becomes the new rightmost.  
  */  
 public int merge(HashMap<Integer, Integer> map, int l, int r) {  
   int left = l - map.get(l) + 1;  
   int right = r + map.get(r) - 1;  
   int range = right - left + 1;  
   map.put(left, range);  
   map.put(right, range);  
   return range;  
 }  
   
 public int longestConsecutive(int[] nums) {  
   // Map each number to the maxLen of the range that contains the number.  
   // Only need to maintain length of range boundaries  
   // since each time we either merge from left or merge from right.  
   HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  
   int maxLen = (nums.length==0) ? 0 : 1;  
   for (int num : nums) {  
     if (!map.containsKey(num)) {  
       map.put(num, 1);  
       if (map.containsKey(num-1)) {  
         maxLen = Math.max(maxLen, merge(map, num-1, num));  
       }  
       if (map.containsKey(num+1)) {  
         maxLen = Math.max(maxLen, merge(map, num, num+1));  
       }  
     }  
   }  
   return maxLen;  
 }  

https://reeestart.wordpress.com/2016/06/14/google-longest-consecutive-sequencesubstring/

leetcode原题就不多说了。HashSet with remove, 虽然有两层loop，但是time complexity还是O(n).

Code for Sequence

  public int longestConsecutive(int[] nums) {

    if (nums == null || nums.length == 0) {

      return 0;

    }

     

    Set<Integer> set = new HashSet<>();

    for (int num : nums) {

      set.add(num);

    }

     

    int result = 0;

    for (int num : nums) {

      set.remove(num);

      int l = num - 1;

      int r = num + 1;

      int len = 1;

      while (set.contains(l)) {

        set.remove(l);

        l--;

        len++;

      }

      while (set.contains(r)) {

        set.remove(r);

        r++;

        len++;

      }

       

      result = Math.max(result, len);

    }

    return result;

  }

Code for Substring

  public int longestConsecutive(int[] nums) {

    if (nums == null || nums.length == 0) {

      return 0;

    }

    int result = 0;

    int len = 1;

    for (int i = 1; i < nums.length; i++) {

      if (nums[i] == nums[i - 1] + 1) {

        len++;

      }

      else {

        result = Math.max(result, len);

        len = 1;

      }

    }

    result = Math.max(result, len);

    return result;

  }

http://www.geeksforgeeks.org/longest-consecutive-subsequence/

X. Union-find
https://xiangliangyang.gitbooks.io/leetcode/content/411-union-find/55-longest-consecutive-sequence.html

https://leetcode.com/problems/longest-consecutive-sequence/discuss/41062/My-Java-Solution-using-UnionFound

    Map<Integer, Integer> map = new HashMap<>(); // parent
    Map<Integer, Integer> c = new HashMap<>(); // count
    int res=1;
    
    public int longestConsecutive(int[] a) {
        if(a.length==0) return 0;
        for(int i=0;i<a.length;i++){ 
            int cur = a[i];
            if(map.containsKey(cur)) continue;

            map.put(cur,cur);
            c.put(cur, 1);
            
            if(map.containsKey(cur-1)) union(cur-1, cur);
            if(map.containsKey(cur+1)) union(cur+1, cur);
        }

        return res;
    }
    
    int find(int x){
        if(map.get(x)==x) return x;
        int par = find(map.get(x));
        map.put(x, par); // path compression
        return par;
    }
    
    void union(int x, int y){
        int px = find(x);
        int py = find(y);
        
        // union by size
        int newCount = c.get(py)+c.get(px);
        if(c.get(px)<c.get(py)){
            map.put(px, py);    
            c.put(py, newCount); 
        }else{
            map.put(py, px);    
            c.put(px, newCount); 
        }
        
        res=Math.max(res, newCount);
    }

http://www.jianshu.com/p/e6b955ca208f

我提前做了一个size数组专门用来记录大小，并且当合并树的时候可以使该算法更快。
当我们需要根据value将index连接起来，而index又相邻时，
Union Find 用代码解决了这个 连接结点 的问题。

参考网址：
http://www.programcreek.com/2013/01/leetcode-longest-consecutive-sequence-java/

  public int longestConsecutive(int[] nums) {

    if (nums == null || nums.length == 0)

      return 0;

    Union union = new Union(nums.length);

    HashMap<Integer, Integer> helper = new HashMap<Integer, Integer>();

    for (int i = 0; i < nums.length; i++) {

      if (helper.containsKey(nums[i])) {

        continue;

      }

      helper.put(nums[i], i);

      if (helper.containsKey(nums[i] - 1))

        union.union(i, helper.get(nums[i] - 1));

      if (helper.containsKey(nums[i] + 1))

        union.union(i, helper.get(nums[i] + 1));

    }

    return union.maxUnion();

  }

  private class Union {

    int[] unions;

    int[] size;

    int count;

    Union(int n) {

      unions = new int[n];

      size = new int[n];

      count = n;

      for (int i = 0; i < n; i++) {

        unions[i] = i;

        size[i] = 1;

      }

    }

    /** return the group id of this index */

    int find(int p) {

      if (p >= unions.length)

        return -1;

      while (p != unions[p])

        p = unions[p];

      return p;

    }

    /** test whether two indexs are connectted */

    boolean connected(int p, int q) {

      p = find(p);

      q = find(q);

      return p == q;

    }

    /** connect two components by making their group id equal */

    void union(int p, int q) {

      p = find(p);

      q = find(q);

      if (size[p] > size[q]) {

        size[p] += size[q];

        unions[q] = p;

      } else {

        size[q] += size[p];

        unions[p] = q;

      }

      count--;

    }

    /** return the maximum size of components */

    int maxUnion() {

      int max = 1;

      for (int i = 0; i < unions.length; i++) {

        max = Math.max(max, size[i]);

      }

      return max;

    }

  }

http://blog.csdn.net/dm_vincent/article/details/7655764

https://discuss.leetcode.com/topic/29286/my-java-solution-using-unionfound/3
http://algs4.cs.princeton.edu/15uf/

I implemented the following code which is a slight improvement over the one suggested in the original post. I have optimized the retrieval of the maxUnion (getHighestRank in my case) to O(1).

Also, @liangyue268 Weighted Union Find with Path Compression isn't exactly O(nlogn) but more close to O(n). This is because the path compression function (see find operation) exhibits growth which follows the Inverse Ackermann Function. Both union and find are not exactly 1 but are very very very close to 1, visit here for more details.

    public int longestConsecutive(int[] nums) {
        final int length = nums.length;
        if (length <= 1) return length;
        
        final Map<Integer, Integer> elementIndexMap = new HashMap();
        final UnionFind uf = new UnionFind(length);
        for (int p = 0; p < length; p++) {
            final int i = nums[p];
            if (elementIndexMap.containsKey(i)) continue;
            if (elementIndexMap.containsKey(i+1)) uf.union(p, elementIndexMap.get(i+1));
            if (elementIndexMap.containsKey(i-1)) uf.union(p, elementIndexMap.get(i-1));
            elementIndexMap.put(i, p);
        }
        return uf.getHighestRank();
    }
    
    private final class UnionFind {
        final private int[] sequenceTree;
        final private int[] rank;
        private int highestRank;
        
        UnionFind(int length) {
            sequenceTree = new int[length];
            rank = new int[length];
            highestRank = 1;
            for (int i = 0; i < length; i++) {
                sequenceTree[i] = i;
                rank[i] = 1;
            }
        }
        
        void union(int p, int q) {
            final int pId = find(p); final int qId = find(q);
            
            if (pId == qId) return;
            
            int localHighestRank = 1;
            if (rank[pId] < rank[qId]) {
                sequenceTree[pId] = qId;
                rank[qId] += rank[pId];
                localHighestRank = rank[qId];
            } else {
                sequenceTree[qId] = pId;
                rank[pId] += rank[qId];
                localHighestRank = rank[pId];
            }
            highestRank = Math.max(highestRank, localHighestRank);
        }
        
        int find(int p) {
            while (p != sequenceTree[p]) {
                sequenceTree[p] = sequenceTree[sequenceTree[p]];
                p = sequenceTree[p];
            }
            return p;
        }
        
        int getHighestRank() { return highestRank; }
    }

        public int longestConsecutive(int[] nums) {
            UF uf = new UF(nums.length);
            Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // <value,index>
            for(int i=0; i<nums.length; i++){
                if(map.containsKey(nums[i])){
                    continue;
                }
                map.put(nums[i],i);
                if(map.containsKey(nums[i]+1)){
                    uf.union(i,map.get(nums[i]+1));
                }
                if(map.containsKey(nums[i]-1)){
                    uf.union(i,map.get(nums[i]-1));
                }
            }
            return uf.maxUnion();
        }
    }
    
    class UF{
        private int[] list;
        public UF(int n){
            list = new int[n];
            for(int i=0; i<n; i++){
                list[i] = i;
            }
        }
        
        private int root(int i){
            while(i!=list[i]){
                list[i] = list[list[i]];
                i = list[i];
            }
            return i;
        }
        
        public boolean connected(int i, int j){
            return root(i) == root(j);
        }
        
        public void union(int p, int q){
          int i = root(p);
          int j = root(q);
          list[i] = j;
        }
        
        // returns the maxium size of union
        public int maxUnion(){ // O(n)
            int[] count = new int[list.length];
            int max = 0;
            for(int i=0; i<list.length; i++){
                count[root(i)] ++;
                max = Math.max(max, count[root(i)]);
            }
            return max;
        }

X.

  public int longestConsecutive(int[] nums) {

    if (nums.length == 0) {

      return 0;

    }

    Arrays.sort(nums);

    int longestStreak = 1;

    int currentStreak = 1;

    for (int i = 1; i < nums.length; i++) {

      if (nums[i] != nums[i - 1]) {

        if (nums[i] == nums[i - 1] + 1) {

          currentStreak += 1;

        } else {

          longestStreak = Math.max(longestStreak, currentStreak);

          currentStreak = 1;

        }

      }

    }

    return Math.max(longestStreak, currentStreak);

  }

X. DP
http://fisherlei.blogspot.com/2013/02/leetcode-longest-consecutive-sequence.html
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:       } 

X. https://leetcode.com/articles/longest-consecutive-sequence/

Time complexity : $O(n^3)$.

The outer loop runs exactly $n$ times, and because currentNum increments by 1 during each iteration of the while loop, it runs in $O(n)$ time. Then, on each iteration of the while loop, an $O(n)$ lookup in the array is performed. Therefore, this brute force algorithm is really three nested $O(n)$ loops, which compound multiplicatively to a cubic runtime.

  private boolean arrayContains(int[] arr, int num) {

    for (int i = 0; i < arr.length; i++) {

      if (arr[i] == num) {

        return true;

      }

    }

    return false;

  }

  public int longestConsecutive(int[] nums) {

    int longestStreak = 0;

    for (int num : nums) {

      int currentNum = num;

      int currentStreak = 1;

      while (arrayContains(nums, currentNum + 1)) {

        currentNum += 1;

        currentStreak += 1;

      }

      longestStreak = Math.max(longestStreak, currentStreak);

    }

    return longestStreak;

  }

Read full article from Jiaxin's LeetCode: Longest Consecutive Sequence @LeetCode