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

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Analysis

Method 1: https://leetcode.com/problems/longest-consecutive-sequence/solution/

Method 2: https://www.youtube.com/watch?v=F4W6l4JKs30

Solution from Forum

Method 1

public int longestConsecutive(int[] nums) {
    Set<Integer> num_set = new HashSet<Integer>();
    for (int num : nums) {
        num_set.add(num);
    }

    int longestStreak = 0;

    for (int num : num_set) {
        if (!num_set.contains(num-1)) {
            int currentNum = num;
            int currentStreak = 1;

            while (num_set.contains(currentNum+1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

Method 2:

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