128. 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.

Solution:

1. Use a HashSet to store all the numbers.

2. Go through the input array, for every number, do:

  a) set count = 1

  b) continuously increasing the number and check if the new number is in the HashSet.

  c) continuously decreasing the number and check if the new number is in the HashSet.

  d) If the new number exists, increase the count  and remove the new number from the HashSet.

  e) Update the max value of count.

3. Output max value of count.

The time complexity is O(n) since and the space complexity is O(n) as well.



Code:

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int max = 1;
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
            }
        }
        for (int num : nums) {
            if (set.contains(num)) {
                int count = 1;
                int up = num + 1;
                int down = num - 1;
                while (set.contains(up)) {
                    count++;
                    set.remove(up);
                    up++;
                }
                while (set.contains(down)) {
                    count++;
                    set.remove(down);
                    down--;
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}