Leetcode 128. Longest Consecutive Sequence

Clarification

Let me first restate the problem to make sure I understand it correctly. We're given an unsorted integer array nums, and we need to find the length of the longest sequence of consecutive integers.

Example.

Can the array contain duplicates?
What's the range of the integers?
The sequence doesn't need to maintain the relative order of nums, does it?

Brute-force Approach

The simple idea is that to sort the array first, and then calculate the length of each consecutive sequence and keep track of the max length while looping the sorted array. This gives us O(nlogn) time because of the sorting operation. The space would be O(1).

Optimized Approach

If time matters, we should try to reduce time to O(n). So I immediately think about using hash map.

First I'll put every number into a set so that I can instantly check whether a number exists. Here's the key observation. Suppose I'm looking at 1, 2, 3, 4. I start counting from every element: 1 -> 2 -> 3 -> 4, 2 -> 3 -> 4, 3 -> 4, 4, I'm doing repeated work. Instead, I only want to start counting from the beginning of a sequence. So how do I know a number is the beginning? A number is the start of a sequence if num - 1 doesn't exist. For example, 1 is a start because 0 is not in the set. 2 is not because 1 exists. So I skip it. Finally for each valid starting point, I extend the sequence until it ends and track the maximum length.

The time complexity would be O(n) even though there is a while loop in for loop. Because we skip non-starting point and only traversed a sequence at the starting point. So every number participates in at most one expansion, which is O(n). The space would be O(n) because we use a hash set.

Code

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numbers = new HashSet<>();

        for (int num : nums) {
            numbers.add(num);
        }

        int longest = 0;

        for (int num : numbers) {

            // only start from the beginning
            if (!numbers.contains(num - 1)) {

                int current = num;
                int length = 1;

                while (numbers.contains(current + 1)) {
                    current++;
                    length++;
                }

                longest = Math.max(longest, length);
            }
        }

        return longest;
    }
}

Follow-up