DSA AnimatorDSA animations
Longest Consecutive Sequence LC #128 Medium HashSet
Problem

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 sequence is [1,2,3,4] with length 4.
Constraints: 0 ≤ nums.length ≤ 10⁵  |  −10⁹ ≤ nums[i] ≤ 10⁹  |  Must run in O(n)
Try Examples
Custom:
Approach
HashSet — Find Sequence Starts
Add all numbers to a HashSet. A sequence 'start' is a number with no predecessor (num-1 not in set). From each start, count how far the consecutive chain extends. Each number is visited at most twice — O(n).
Array
Input: nums[] — cells colored by role at current step
HashSet (O(1) lookups)
Variables
cur (num)
—
streak len
—
maxLen
—
isStart?
—
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Add all numbers to a HashSet for O(1) lookup
2
Find sequence starts: nums where (num−1) is not in set
3
From each start, count consecutive run using set.contains(cur+1)
4
Track and return maxLen across all streaks
Time
O(n)
Space
O(n)
Why It Works

By storing all numbers in a HashSet, we get O(1) contains checks. We only start counting from a number that has no predecessor — this guarantees we never recount the same sequence from the middle. Even though there is a while loop inside the for loop, each number is touched at most twice total, keeping the overall complexity O(n).

How to solve Longest Consecutive Sequence

LeetCode 128 · Medium · Arrays · Pattern: Hash Set

Why the obvious approach is slow

Sorting first costs O(n log n). And counting up from every single number repeats the same work again and again.

The key idea

Put every number in a hash set. Only start counting from a number that begins a run, meaning the number −1 is not in the set. Then count up while the next number exists.

Remember

Only count from the start of a run, where x −1 is missing. That keeps the whole thing linear.

Run the animation above on your own input, or watch the 1:23 video explanation of Longest Consecutive Sequence with a dry run and Java code.

More Arrays problems