Longest Consecutive Sequence

Problem

Given an unsorted array of integers nums, return the length of the longest run of consecutive integer values that all appear somewhere in the array. The values only need to exist in the array — their positions don’t matter, and duplicates count once.

The required time complexity is O(n), which rules out sorting as the final solution.

Examples

Example 1: nums = [100, 4, 200, 1, 3, 2] → 4 The values 1, 2, 3, 4 all appear, forming a consecutive run of length 4; 100 and 200 are isolated.

Example 2: nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] → 9 Every value 0 through 8 appears (the duplicate 0 counts once), a run of length 9.

Example 3: nums = [] → 0 No elements, no run.

Constraints

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

With up to 10^5 elements and values up to 10^9, a counting array over the value range is infeasible, and quadratic scans (~10^10 operations) are too slow. The O(n) requirement is the core constraint.

Think about it first

TL;DR

Hash set + start-of-run detection — O(n) time, O(n) space.

Approach 1 — Brute force (walk up from every element)

For each value, check whether value+1 is present by scanning the array, and extend as far as possible.

from typing import List


def longestConsecutive(nums: List[int]) -> int:
    best = 0
    for v in nums:
        length = 1
        while v + length in nums:   # O(n) list scan per probe
            length += 1
        best = max(best, length)
    return best

Complexity: each in nums on a list is O(n), each walk is up to O(n) probes, over n starts: O(n³) worst case, O(1) space. At n = 10^5 that’s ~10^15 operations — hopeless.

Approach 2 — Sort, then scan runs

After sorting, the values of a consecutive run sit next to each other, so a single linear scan finds the longest run. Skip duplicates instead of resetting on them.

from typing import List


def longestConsecutive(nums: List[int]) -> int:
    if not nums:
        return 0
    nums.sort()
    best = 1
    current = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            continue                     # duplicate: run unchanged
        if nums[i] == nums[i - 1] + 1:
            current += 1
        else:
            current = 1
        best = max(best, current)
    return best

Walkthrough on Example 1, nums = [100, 4, 200, 1, 3, 2]:

1. Sorted: [1, 2, 3, 4, 100, 200].
2. 2 = 1+1 → current 2; 3 = 2+1 → current 3; 4 = 3+1 → current 4 (best 4).
3. 100 ≠ 4+1 → reset to 1; 200 ≠ 100+1 → reset to 1.
4. Answer: 4.

Complexity: O(n log n) time for the sort, O(1) extra space (in-place). Correct and simple, but it misses the problem’s stated O(n) requirement.

Approach 3 — Hash set with start-of-run detection

A set gives O(1) membership, but walking upward from every element still re-traverses each run once per member (O(n²) worst case, e.g. [1..n]). Only start a walk from a run’s left endpoint: a value v with v - 1 absent from the set. Each run is then walked exactly once, and every element is touched O(1) times overall.

from typing import List


def longestConsecutive(nums: List[int]) -> int:
    values = set(nums)
    best = 0
    for v in values:
        if v - 1 in values:
            continue                 # not a run start
        length = 1
        while v + length in values:
            length += 1
        best = max(best, length)
    return best

Walkthrough on Example 1, values = {1, 2, 3, 4, 100, 200}:

1. v = 1: 0 not in set, so it is a run start. 2, 3, 4 present; 5 absent → length 4, best = 4.
2. v = 2, 3, 4: each has its predecessor in the set → skipped in O(1).
3. v = 100: 99 absent → start; 101 absent → length 1.
4. v = 200: 199 absent → start; 201 absent → length 1.
5. Answer: 4.

Complexity: O(n) time — the start-check is O(1) per element, and all upward probes combined touch each set member once (each element belongs to exactly one run). O(n) space for the set.

Common pitfalls

• Skipping the v - 1 not in values guard — the code still returns the right answer but degrades to O(n²) on an already-consecutive array, which is precisely the case the problem tests.
• Doing membership tests against the list instead of a set — same silent complexity blowup (O(n) per probe).
• Forgetting duplicates: in the sorting approach, nums[i] == nums[i-1] must neither extend nor reset the run; the set approach dedupes for free.
• Not handling the empty array (return 0, not a crash on max of nothing).

Pattern takeaway

A hash set turns “does value x exist?” into an O(1) check. Just as important, pick canonical starting points (here, run left endpoints) so total work is charged once per element instead of once per pair. O(1) membership plus walking only from boundaries is a standard route to linear time on value-adjacency problems.