Leetcode/F家，G家 -- 128. Longest Consecutive Sequence(HashMap+UnionFind)

128. Longest Consecutive Sequence

• Difficulty: Hard

https://leetcode.com/problems/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

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

思路： 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 class Solution {
    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;
    }
}