Longest Consecutive Sequence

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

Have you met this question in a real interview? 

Yes

Example

Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Clarification

Your algorithm should run in O(n) complexity.

public class Solution {

    /**

     * @param nums: A list of integers

     * @return an integer

     */

    public int longestConsecutive(int[] nums) {

        // write you code here

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

        for(int num : nums){

            set.add(num);

        }

        int maxCount = 0;

        for(int num : nums){

            int left = num - 1;

            int right = num + 1;

            int count = 1;

            if(!set.contains(num))

                continue;

            set.remove(num);

            while(set.contains(left)){

                set.remove(left);

                left--;

                count++;

            }

            

            while(set.contains(right)){

                set.remove(right);

                right++;

                count++;

            }

            

            maxCount = Math.max(count, maxCount);

            

           

        }

        return maxCount;

    }

}