Longest Consecutive Sequence

mediumTests passed 2026-11-11v1.0.0

TC: O(N)|SC: O(N)

Arrays & Hashing Original Statement (leetcode).md

1. Core Invariant / The Trick

Put all numbers in a Set. Iterate over set elements (not the raw array to skip duplicates), and ONLY start expanding `x, x+1, x+2...` if `x - 1` is NOT in the set (marking `x` as a sequence head).

2. Complexity Bounds & Proof

Every element in the set is visited at most twice (once in outer loop, at most once in inner expansion from its sequence start).

3. Minimal Idiomatic Code

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    best = 0
    for x in num_set:
        if x - 1 not in num_set:
            length = 1
            while x + length in num_set:
                length += 1
            best = max(best, length)
    return best

4. Failure Modes & Interview Follow-ups

Pitfalls:- Iterating over `nums` instead of `numSet` causes O(N^2) if a sequence head is duplicated many times.

Follow-ups:- Dynamic stream additions: maintain interval boundaries `{ num: length }` merging `left` and `right` endpoints.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Number of Connected Components in an Undirected Graph (O(V + E * a(V)))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.