package code;

import java.util.HashSet;
import java.util.Set;

/*
 * 128. Longest Consecutive Sequence
 * 
 * Hard
 * Array, Union Find
 * setremove
 * Tips
 */
public class lc128 {
    public static void main(String[] args) {
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(longestConsecutive(nums));
    }
    public static int longestConsecutive(int[] nums) {
        Set s = new HashSet();
        for(int i:nums) s.add(i);
        int max_len = 0;
        for(int i:nums) {
            if(s.contains(i)){
                s.remove((Integer)i);
                int left = i-1;
                while(s.contains(left)){
                    s.remove((Integer)left);
                    left--;
                }
                int right = i+1;
                while(s.contains(right)){
                    s.remove((Integer)right);
                    right++;
                }
                max_len = Math.max(right-left-1, max_len);
            }
        }
        return max_len;
    }
}