Longest Consecutive Sequence

Longest Consecutive Sequence

What is this problem about?

The Longest Consecutive Sequence interview question gives you an unsorted array of integers and asks you to find the length of the longest sequence of consecutive numbers. The catch? You must solve it in $O(N)$ time complexity. For example, given [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4], and its length is 4.

Why is this asked in interviews?

This is a classic Hash Table problem that frequently appears in interviews at top tech companies. It is brilliant for evaluating a candidate's understanding of algorithmic time complexity. The naive reaction is to sort the array and count, but sorting takes $O(N \log N)$ time. The interviewer wants to see if you can utilize constant-time data structure lookups to break through the sorting bottleneck.

Algorithmic pattern used

This problem perfectly illustrates the Hash Set pattern. The trick is to dump all numbers into a Hash Set to achieve $O(1)$ lookups. Then, you iterate through the set. To ensure you aren't doing redundant work, you only start counting a sequence if the current number is the start of a sequence—meaning current_number - 1 does NOT exist in the set. From there, you simply count upwards current_number + 1, + 2, etc., tracking the sequence length.

Example explanation

Let's use the array [100, 4, 200, 1, 3, 2].

1. Convert to a set: {100, 4, 200, 1, 3, 2}.
2. Iterate through the set:
   • Look at 100. Is 99 in the set? No. It's a sequence starter. Count up: 101 isn't there. Length = 1.
   • Look at 4. Is 3 in the set? Yes. So 4 is NOT a starter. Skip.
   • Look at 200. Is 199 in the set? No. Starter. Length = 1.
   • Look at 1. Is 0 in the set? No. Starter. Count up: 2 is there, 3 is there, 4 is there, 5 is not. Length = 4.
   • Look at 3 and 2. Both have their predecessors (2 and 1) in the set, so we skip them. The max length we found was 4.

Common mistakes candidates make

The number one mistake candidates make is sorting the array, which immediately fails the $O(N)$ time complexity requirement. Even when candidates use a Hash Set, they often forget the crucial check (if !set.contains(num - 1)). Without this check, the algorithm will attempt to count sequences starting from the middle, degrading the performance back to $O(N^2)$ in the worst-case scenario.

Interview preparation tip

When preparing for the Longest Consecutive Sequence coding pattern, deeply internalize the "sequence starter" logic. In $O(N)$ Hash Set problems, the key to efficiency is knowing what to skip. Asking "Is this the beginning of a chain?" prevents overlapping work and keeps your algorithms strictly linear.