Longest Consecutive Sequence

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

Your algorithm should run in O(n) complexity.

Example:

Given [100, 4, 200, 1, 3, 2],

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

Solution:

This is a great question for practicing HashSet. Finding elemnt in an hashset is only cost O(1), therefore, we should add all numbers in given array to an HashSet.

Then, we run through each number to find the longest consecutive sequence. For a arbitary number, a consecutive sequence could be found based on this number by increasing and decreasing by one at a time iteratively. Then we could calculate the length of this consecutive sequence by the distance between the smallest and largest numbers in this sequence.

However, the complexity is still O(n^n) at this moment. We could further improve it to O(n) by removing the element after we visited it during finding consecutive sequence process.

Code:

public class Solution {

    public int longestConsecutive(int[] num) {
        HashSet<Integer> set = new HashSet<>();
        for (int x : num) {
            set.add(x);
        }
        int longest = 0;
        for (int x : num) {
            int down = x - 1;
            while (set.contains(down)) {
                set.remove(down);
                down--;
            }
            int up = x + 1;
            while (set.contains(up)) {
                set.remove(up);
                up++;
            }
            longest = Math.max(longest, up - down - 1);
        }
        return longest;
    }
}