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.

The idea is to use a set to check the left boundary and right boundary of a number in the array.

Check each number's left and right boundary, if found remove it from the set and increase the count. Keep finding until the boundary is not in the array. Since we will only use set to find the boundary once, the overall running time is O(n).

public int longestConsecutive(int[] num) {
        Set<Integer> results = new HashSet<Integer>();

        //n
        for (int number : num) {
            results.add(number);
        }

        int max = 1;
        //n+ 1*n = 2n
        for (int number: num) {
            int left = number-1;
            int right = number+1;
            int count = 1;
            //we need to remove the left and right boundary so it is only found once.
            while (results.contains(left)) {
                results.remove(left);
                left = left-1;
                count = count+1;
            }

            while (results.contains(right)) {
                results.remove(right);
                right = right + 1;
                count = count+1;
            }

            max = Math.max(count, max);

        }

        return max;
    }