Longest Consecutive Sequence: O(n) Hash Set Solution Explained

Longest Consecutive Sequence (LeetCode #128) is one of those problems that makes you reach for sort() on instinct. Given an unsorted array of integers, find the length of the longest consecutive elements sequence. The twist? You must do it in O(n) time.

The problem is rated Medium, but the optimal solution is genuinely elegant. Instead of sorting, you drop every number into a hash set and then use a single check — "is num-1 in the set?" — to ensure you only start counting from the beginning of each sequence. That one insight is what makes the entire solution work.

In this walkthrough, you will understand why sorting falls short, how the hash set approach achieves true O(n), and what edge cases to watch for in interviews. If you have seen this problem before but could not explain why it is O(n), this article will make it click.

You are given an unsorted array of integers. Your goal is to find the length of the longest sequence of consecutive numbers. The elements do not need to be adjacent in the array — they just need to form a consecutive run when arranged in order.

For example, given [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], so you return 4. The numbers 100 and 200 are isolated — they do not connect to any longer chain.

The critical constraint is time complexity: the solution must run in O(n). This immediately rules out any approach that sorts the array, since comparison-based sorting is O(n log n) at best. You need a fundamentally different strategy.

The most intuitive approach is to sort the array and scan for consecutive runs. After sorting, you walk through the array with a counter: if the current number is exactly one more than the previous, increment the streak; if it is the same, skip it; otherwise, reset the streak.

This works correctly and is easy to implement. For [100, 4, 200, 1, 3, 2], sorting gives [1, 2, 3, 4, 100, 200]. You scan and find the streak 1-2-3-4 with length 4. The problem is that sorting costs O(n log n), which violates the O(n) requirement.

In an interview, mentioning the sort approach first is fine — it shows you understand the problem. But you need to follow it with the optimal hash set solution to demonstrate that you can think beyond the obvious.

The optimal approach uses a hash set for O(1) lookups. First, insert every number from the array into a set. Then iterate through the set, and for each number, check whether num-1 exists in the set. If it does, skip this number — it is not the start of a sequence. If num-1 is NOT in the set, you have found a sequence beginning.

When you find a sequence start, count upward: check for num+1, num+2, num+3, and so on until the chain breaks. Track the maximum length you find across all sequence starts. That maximum is your answer.

Here is the logic in plain English. For the array [100, 4, 200, 1, 3, 2], the set contains {1, 2, 3, 4, 100, 200}. When you reach 1, you check: is 0 in the set? No — so 1 is a sequence start. Count up: 2 is in the set, 3 is in the set, 4 is in the set, 5 is not. The streak from 1 is length 4. When you reach 2, 3, or 4, you check num-1 and find it in the set, so you skip them entirely.

The algorithm in steps: (1) Add all numbers to a hash set. (2) For each number in the set, check if num-1 is absent. (3) If absent, count consecutive numbers starting from num. (4) Update the global maximum. (5) Return the maximum.

At first glance, the nested loop — an outer loop over all numbers and an inner while loop counting upward — looks like it could be O(n^2). But it is not, because of the sequence-start check.

The key observation is that the inner counting loop only runs when num-1 is NOT in the set. This means you only start counting from the very beginning of each sequence. A number in the middle or end of a sequence is skipped in constant time by the num-1 check.

Consider what happens across the entire iteration. Every number in the array is "touched" at most twice: once in the outer loop (where it either gets skipped or starts a count), and at most once in some inner counting loop (when a different sequence start counts through it). Two passes over n elements is still O(n).

Building the hash set takes O(n). The combined work of the outer loop and all inner counting loops is O(n). Total: O(n) time, O(n) space. The "only start from beginnings" check is not just an optimization — it is the structural guarantee that prevents redundant work.

Interviewers will test your solution against tricky inputs. Make sure you handle each of these correctly before submitting.

An empty array should return 0. A single-element array returns 1 — that one number is a consecutive sequence of length 1. An array where every element is the same, like [7, 7, 7], should return 1 because the hash set deduplicates, leaving just {7}.

Negative numbers work seamlessly because the hash set does not care about sign. The array [-3, -2, -1, 0, 1] has a longest consecutive sequence of length 5. An already-sorted array is not a special case — the hash set approach handles it identically to an unsorted one.

Duplicates deserve extra attention. Because you iterate over the set (not the original array), duplicates are naturally ignored. This is a subtle advantage of using a set over a plain array for the lookup structure.

LeetCode #128 is a masterclass in a single idea: using a hash set for O(1) lookup combined with a clever starting condition to avoid redundant work. The "only count from sequence beginnings" pattern appears in other problems too — anywhere you need to avoid re-processing elements that belong to a chain or group.

This problem also teaches you to question your first instinct. Sorting is the obvious approach, and it works, but it does not meet the constraint. The ability to recognize when a hash set can replace sorting is a skill that transfers to dozens of other problems.

If you found yourself unsure about the O(n) analysis, practice explaining it out loud. Interviewers at Amazon, Google, and Meta will ask you to justify your time complexity, and hand-waving through "each element is visited at most twice" will not cut it — you need to articulate the sequence-start invariant clearly.

Review this problem with YeetCode flashcards to build the pattern recognition you need. The hash set plus starting-condition technique is one of the most reusable tools in your interview toolkit.