Longest Consecutive Sequence

Solving the Longest Consecutive Sequence Problem Like a Pro

Introduction

As experts in algorithms and data structures, we understand the mental gymnastics it can take to go from brute-force to optimal code. Today, we're dissecting the Longest Consecutive Sequence problem — a common coding challenge that tests your understanding of sets, sequences, and time complexity.

Whether you're preparing for a coding interview or building performance-critical applications, knowing how to solve this efficiently can make or break your success.

Problem Statement

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

Sample Test Cases:

Input: [100, 4, 200, 1, 3, 2]         # Output: 4
Input: [0,3,7,2,5,8,4,6,0,1]         # Output: 9
Input: list(range(10**5))           # Output: 100000
Input: list(range(0, 10**6, 2))     # Output: 1
Input: list(range(500000)) + list(range(500000, 1000000))  # Output: 1000000

Brute-Force Approach (And Why It’s Bad)

The naive method tries to count the sequence from the minimum number upward. Here's what that looked like:

from typing import List

def lcs_brute_force(nums: List[int]) -> int:
    max_val = float("inf")
    dp = {}
    count = 1
    
    for i in range(len(nums)):
        if nums[i] < max_val:
            max_val = nums[i]
        if nums[i] not in dp:
            dp[nums[i]] = 1
        else:
            dp[nums[i]] += 1

    val_in = max_val + 1
    while val_in in dp:
        count += 1
        val_in += 1

    return count

Why This Fails:

• It only starts from the smallest number, not any arbitrary sequence.

• It assumes a sequence starts at min(nums) — which is wrong in general.

• Time Complexity: O(N log N) at best, often worse due to hash lookups and the incomplete logic.

Optimal Approach: Set-Based Linear Scan

Core Idea

We use a HashSet to enable constant-time lookups, and only start counting a sequence if the previous number isn’t in the set. This ensures we only visit each number once per sequence.

def longest_consecutive(nums):
    num_set = set(nums)
    max_length = 0

    for num in num_set:
        # Only start counting if `num - 1` is not in the set
        if num - 1 not in num_set:
            current = num
            length = 1

            # Count upward until the sequence ends
            while current + 1 in num_set:
                current += 1
                length += 1

            max_length = max(max_length, length)

    return max_length

Step-by-Step Diagram

Input: [100, 4, 200, 1, 3, 2]

HashSet: {1, 2, 3, 4, 100, 200}

Start at 1 -> 2 -> 3 -> 4 -> (5 not in set)
-> Sequence Length = 4

Other numbers are skipped since 100-1=99 is not in set, but it ends quickly.

Time and Space Complexity

• Time: O(N) – every element is processed once.

• Space: O(N) – we store all unique elements in a set.

Test Results

print("Expected: 4, Actual: ", longest_consecutive([100, 4, 200, 1, 3, 2]))
print("Expected: 9, Actual: ", longest_consecutive([0,3,7,2,5,8,4,6,0,1]))
print("Expected: 100000, Actual: ", longest_consecutive(list(range(10**5))))
print("Expected: 1, Actual: ", longest_consecutive(list(range(0, 10**6, 2))))
print("Expected: 1000000, Actual: ", longest_consecutive(list(range(500000)) + list(range(500000, 1000000))))

Key Takeaways You Can Apply Anywhere

# What data structure did the optimal solution use?

A HashSet (Python set) to allow O(1) lookups.

# What pattern does it use?

Hashing + Sequence Expansion. Only begin counting at sequence starts.

# How could I recognize this pattern in a new problem?

If a problem asks for a sequence or uniqueness in linear time — think set or hash map.

# How could I come up with this solution on my own?

• Ask: What operation is slowing me down? (lookup)

• Think: Can I eliminate rework by remembering what I’ve seen?

• Try: Transform data to make logic simpler (set helps eliminate duplicates and enable O(1) lookup).

Want to Master These Tricks Faster?

The best way to internalize these patterns is deliberate practice. Solve 5–10 similar problems, always asking:

• "What slows down my brute-force?"

• "What property can I exploit?"

• "Can I use hashing to improve time?"

Want to level up faster? Bookmark this pattern — "HashSet for Sequence Tracking" — and revisit it during your next practice session.

Now go solve the next problem — but do it smart, not hard.