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 answer, even though sorting is a fine warm-up.

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

10^5 elements with values up to 10^9: no counting array over the value range, and quadratic scans (~10^10) are out. The O(n) bar is the point of the problem.

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)

The naive intuition: for each value, keep asking “is value+1 also here?” by scanning the array, extending as far as possible.

from typing import List


class Solution:
    def longestConsecutive(self, 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

The insight: after sorting, a consecutive run of values sits contiguously, so one linear scan finds the longest run — just skip duplicates rather than resetting on them.

from typing import List


class Solution:
    def longestConsecutive(self, 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 — it just misses the problem’s stated O(n) bar.

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

The insight: 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]). The fix: only launch 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


class Solution:
    def longestConsecutive(self, 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 → run start. Probe 2 ✓, 3 ✓, 4 ✓, 5 ✗ → 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 O(1), but the pattern’s second half matters just as much: pick canonical starting points (here, run left-endpoints) so that aggregate work is charged once per element instead of once per element-pair. “O(1) membership + walk only from boundaries” is the standard route to linear time on value-adjacency problems.