128. Longest Consecutive Sequence

Problem¶

Given an unsorted integer list, return the length of its longest sequence of consecutive values. Duplicates do not extend a sequence, and the algorithm must run in expected \(O(n)\) time.

nums = [100, 4, 200, 1, 3, 2] -> [1, 2, 3, 4] -> 4

Key trick¶

Put all values in a set and only start counting from a value whose predecessor is absent; this ensures each sequence is traversed once.

Trap¶

• Sorting takes \(O(n \log n)\) instead of the required \(O(n)\).
• Starting a scan from every value can degrade to \(O(n^2)\).
• Allocating an array from the minimum to maximum value wastes memory when the values are sparse.
• Duplicates must not increase the sequence length.
• This is not longest increasing subsequence because input order is irrelevant.

Why is it interesting?¶

It turns a global sequence problem into constant-time membership checks and avoids repeated work by identifying sequence starts.

Python solution¶

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        values = set(nums)
        best = 0

        for x in values:
            # Only the smallest value of a sequence begins a scan.
            if x - 1 in values:
                continue

            cnt = 0
            while x in values:
                cnt += 1
                x += 1

            best = max(best, cnt)

        return best

• Time: expected \(O(n)\)
• Space: \(O(n)\)

Comment on my solution¶

Your direct-address array correctly finds consecutive runs, but its size is determined by the numeric range rather than the number of inputs.

Let \(R = \max(nums) - \min(nums) + 1\):

• Time: \(O(n + R)\)
• Space: \(O(R)\)

For sparse values such as \(-10^9\) and \(10^9\), it attempts to allocate roughly two billion entries, causing the memory limit error. The set approach stores only values that actually occur.

# WRONG
# Memory Limit Exceeded 72 / 85 testcases passed
# [0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999]
class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        # [100,4,200,1,3,2] -> 4
        # [0,3,7,2,5,8,4,6,0,1] -> 9
        # [1,0,1,2] -> 3
        if not nums:
            return 0
        lo = min(nums)
        hi = max(nums)
        arr = [None] * (hi - lo + 1)
        for x in nums:
            arr[x - lo] = x
        best = 1
        i = 0
        while i < len(arr):
            j = i
            while j < len(arr) and arr[j] is not None:
                j += 1
            best = max(best, j - i)
            while j < len(arr) and arr[j] is None:
                j += 1
            i = j
        return best