HARD Lab · Arrays & Hashing · 05

128. Longest Consecutive Sequence

Find the length of the longest run of consecutive integers in an unsorted array — in O(n)time by using a hash set to skip anything that isn't the first number of its run.

● MediumHash SetTypeScript

PROBLEM What we're solving

Given an unsorted array of integers, return the length of the longest consecutive sequence (e.g. 4, 5, 6, 7has length 4). Duplicates don't extend a run. For [100, 4, 200, 1, 3, 2] the answer is 4 — the sequence 1, 2, 3, 4.

KEY IDEA Only start counting from sequence beginnings

Insight → a value v is the start of a consecutive run iff v - 1 is not in the set. Skip every other value. Then walk v, v+1, v+2, … with O(1) set lookups until the chain breaks. Each value is visited at most once total, giving O(n) — no sorting needed.

RECIPE Build set, find starts, walk runs

  • 0 · Load into a Set. new Set(nums) takes O(n) and gives O(1) lookups. Duplicates collapse — that's fine.
  • 1 · Iterate. For each value v in the set, check if v - 1 is present.
  • 2 · Skip non-starts. If set.has(v - 1), v is a middle/end value — skip it entirely. This is the key savings.
  • 3 · Walk the run. From a start, increment cur while set.has(cur + 1), counting the length.
  • 4 · Track best. best = Math.max(best, run) after each run ends.
Classic confusion →the natural impulse is to sort and scan linearly — that's O(n log n). The hash-set approach is O(n) because each number participates in exactly one walk: the walk that starts at its run's minimum. All others are skipped before a while loop even begins.

COST Complexity & alternatives

Sort, then scan
O(n log n)
Simple, but sorting dominates.
Hash set + start check
O(n)
O(n) time; O(n) space for the set.

Why the inner while isn't O(n²)

The while loop looks like it could walk O(n) per start. But we only enter a walk from a sequence start. Each element belongs to exactly one run and is visited at most once across all walks. Total work is O(n).

Pattern transfer →the "only process from the boundary" insight recurs in Number of Islands (flood-fill each island once), Graph Valid Tree (only start a DFS from unvisited nodes), and Missing Number(mark what's present, report what's absent). Whenever you catch yourself about to sort an array to find runs or intervals, ask: "Can a set skip redundant work?"

RUN IT Only start from sequence beginnings — skip the middle

step 0 / 13
STARTBuild a Set from [100, 4, 200, 1, 3, 2]. O(1) membership checks let us avoid sorting entirely.
nums1004200132
State
6
set size
0
best
sequence startrun being countedbest (answer)
slowfast

TYPESCRIPT The solution, annotated

longestConsecutive.ts
function longestConsecutive(nums: number[]): number {
  const set = new Set<number>(nums);
  let best = 0;

  for (const v of set) {
    // Only begin a walk from sequence STARTS (no left neighbour).
    if (set.has(v - 1)) continue;

    let cur = v;
    let run = 1;
    while (set.has(cur + 1)) {
      cur++;
      run++;
    }

    best = Math.max(best, run);
  }

  return best;
}

Reading it block by block

Line 2 — build the set. Loading all values into a Set<number>costs O(n) and enables O(1) membership checks everywhere below. Duplicates are silently deduplicated — they can't extend a consecutive run.
Lines 5–6 — iterate and filter starts. We loop over set (not nums) to avoid processing duplicate values twice. if (set.has(v - 1)) continueskips any value that has a left neighbour — it's provably not the start of its run. This single line is responsible for the O(n) guarantee.
Lines 8–12 — walk the run. From a confirmed start, increment cur while the next integer exists in the set. Each step costs O(1). The total steps across all runs equal exactly the number of distinct values, so the total across all iterations is O(n).
Line 14 — update best. After each run collapses, compare its length to the running maximum. Math.max is O(1). Return best when done.
Complexity → O(n) time — each value is loaded once and walked at most once (only from its run's start). O(n) space for the hash set. The inner while looks quadratic but the start-check ensures total iterations across all walks equal n.

INTERVIEWFollow-ups they'll ask

  • "Return the actual sequence, not just its length?" Track bestStart alongside best; after the loop reconstruct with Array.from({length: best}, (_, i) => bestStart + i).
  • "What if the array has duplicates?" Duplicates are handled automatically — the set collapses them, and the start-check still works. A run of 1, 1, 2 produces a run of length 2, not 3.
  • "Can you do it without extra space?" Sorting the array takes O(n log n) time and O(1) extra space (in-place), then a single scan finds the longest run of consecutive integers. The hash-set approach trades O(n) space for a better time bound.
  • "What's the brute force?" For each number, do a nums.includes(v + k)scan for k = 1, 2, …. That's O(n²) or O(n³) depending on inner loop implementation.
  • "Union-Find variant?" Each number is a node; union adjacent integers in the set. The largest component size is the answer. Same O(n) amortized, but more complex; useful if the input arrives as a stream.

MNEMONIC The one-liner

"Load into a set; only walk from a number with no left neighbour — every other is already covered."

TRIGGERS When you see ___ → reach for ___

"longest consecutive" or "consecutive run"hash set + start-only walk
unsorted array, O(n) requiredSet for O(1) membership, skip non-starts
temptation to sort firstask: can a set skip the redundant work?
"how many distinct runs / components"start-check + walk per component

SKELETON The reusable shape

skeleton.ts
function longestConsecutive(nums: number[]): number {
  const set = new Set<number>(nums);
  let best = 0;

  for (const v of set) {
    if (set.has(v - 1)) continue;   // skip: not a start

    let cur = v, run = 1;
    while (set.has(cur + 1)) { cur++; run++; }

    best = Math.max(best, run);
  }

  return best;
}

FLASHCARDS Tap to flip

What is the first data structure to build?
A Set<number> from the input array — enables O(1) lookups and collapses duplicates.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What is the time complexity of the hash-set solution?
QUESTION 02
For nums = [100, 4, 200, 1, 3, 2], which values are sequence starts?
QUESTION 03
Why does the algorithm skip a number when set.has(v - 1) is true?
QUESTION 04
What does the algorithm return for nums = [0, -1]?
QUESTION 05
What is the space complexity?
QUESTION 06
If you replaced the hash set with a sorted array, what would the time complexity become?
QUESTION 07
nums = [1, 2, 0, 1] — what does the algorithm return?