Longest Consecutive Sequence

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

You must write an algorithm that runs in O(n) time.

Example 1:

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

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9

Example 3:

Input: nums = [1,0,1,2] Output: 3

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Approach: Hash Set with Sequence Start Detection (Optimal Solution)

Algorithm

1. Add all numbers to a hash set for O(1) lookups
2. For each number, only start counting a sequence if num - 1 is not in the set (i.e., num is the start of a sequence)
3. From a sequence start, keep incrementing while consecutive numbers exist, counting the length
4. Track the maximum length seen

Time & Space Complexity

• Time Complexity: O(n) - each number is visited at most twice (once to check, once to extend a sequence)
• Space Complexity: O(n) - the hash set stores all numbers

Java Implementation

import java.util.HashSet;
import java.util.Set;

public class LongestConsecutiveSequence {

    /**
     * Return the length of the longest consecutive elements sequence.
     * @param nums Unsorted array of integers
     * @return Length of the longest consecutive sequence
     */
    public static int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int longest = 0;

        for (int num : numSet) {
            // Only start a sequence if num is the start of it
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int length = 1;

                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    length++;
                }

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

        return longest;
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        int[] nums1 = {100, 4, 200, 1, 3, 2};
        System.out.println("Input: nums = [100, 4, 200, 1, 3, 2]");
        System.out.println("Output: " + longestConsecutive(nums1)); // Expected: 4

        // Test case 2
        int[] nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
        System.out.println("Input: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]");
        System.out.println("Output: " + longestConsecutive(nums2)); // Expected: 9

        // Test case 3
        int[] nums3 = {1, 0, 1, 2};
        System.out.println("Input: nums = [1, 0, 1, 2]");
        System.out.println("Output: " + longestConsecutive(nums3)); // Expected: 3
    }
}

Example Walkthrough

For nums = [100, 4, 200, 1, 3, 2]:

1. Set = {100, 4, 200, 1, 3, 2}
2. num=100: 99 not in set, so start. 101 not in set. length=1
3. num=4: 3 is in set, so skip (not a start)
4. num=200: 199 not in set. 201 not in set. length=1
5. num=1: 0 not in set, so start. 2, 3, 4 in set. length=4
6. num=3: 2 is in set, so skip
7. num=2: 1 is in set, so skip

Longest = 4.

Key Points

1. O(n) Requirement: Sorting would be O(n log n); the hash set approach achieves O(n)
2. Only Count from Sequence Starts: Checking num - 1 prevents redundant work
3. Duplicate Handling: The set naturally deduplicates repeated numbers
4. Linear Amortized Cost: Each element is examined at most twice across the whole algorithm
5. Edge Cases: Handles empty arrays (returns 0) and single-element arrays (returns 1)