Longest Consecutive Sequence

Difficulty: Medium

Problem

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

Example

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

Brute-force approach

Sort the array and find longest consecutive run.

Steps

1. Sort the array
2. Iterate and count consecutive elements
3. Handle duplicates
4. Track maximum streak

Time complexity: O(n log n) · Space complexity: O(1) or O(n)

Trade-offs

• Sorting takes O(n log n)
• Modifies array (or needs copy)
• Can we avoid sorting?

Optimal approach

Key insight: A number is a sequence START only if (num - 1) is NOT present in the set!

Use a Set for O(1) lookup. Only start counting from sequence beginnings (no predecessor).

Steps

1. Put all numbers into a HashSet
2. Loop through numbers
3. If (num-1) not in set → it's a sequence start
4. Count consecutive numbers from that start
5. Track the longest streak

Time complexity: O(n) · Space complexity: O(n)