Longest Consecutive Sequence in Python | O(n) Optimal Solution Explained (LeetCode 128)

Longest Conseive Sequence – From TLE to Optimal O(n)

The Longest Consecutive Sequence problem looks simple at first, but it easily leads to a Time Limit Exceeded (TLE) error if we are not careful with repeated work. In this post, I’ll explain where the TLE comes from and how a small optimization makes the solution run in linear time.

Problem Overview

Given an unsorted array of integers, we need to find the length of the longest sequence of consecutive numbers. The solution must run in O(n) time.

Initial Thought Process (Why TLE Happens)

A common approach is to check for every number and keep extending the sequence forward (x, x+1, x+2...). While lookup using a hash structure is O(1), the same sequence gets counted multiple times, leading to unnecessary repeated work.

In the worst case (like a fully consecutive array), this turns into O(n²), which causes TLE.

Key Optimization

The fix is surprisingly small but powerful:

• Only start counting when the current number is the start of a sequence
• A number is a start if (n - 1) does not exist in the set

This guarantees that each consecutive sequence is processed only once.

Optimal O(n) Solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0

        for n in num_set:
            if n - 1 not in num_set:
                length = 1
                current = n

                while current + 1 in num_set:
                    current += 1
                    length += 1

                longest = max(longest, length)

        return longest

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Complete Code on GitHub

You can find the full implementation here:

👉 Longest Consecutive Sequence – GitHub Solution

Final Takeaway

This problem is a great example of how being very close to the right idea is often enough. A single condition to avoid duplicate work converts a TLE solution into an optimal one. Recognizing these patterns comes with consistent practice.