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

nums =

step 0 / 13

STARTBuild a Set from [100, 4, 200, 1, 3, 2]. O(1) membership checks let us avoid sorting entirely.

1function longestConsecutive(nums: number[]): number {
2▶  const set = new Set<number>(nums);
3▶  let best = 0;
4 
5  for (const v of set) {
6    // Only begin a walk from sequence STARTS (no left neighbour).
7    if (set.has(v - 1)) continue;
8 
9    let cur = v;
10    let run = 1;
11    while (set.has(cur + 1)) {
12      cur++;
13      run++;
14    }
15 
16    best = Math.max(best, run);
17  }
18 
19  return best;
20}

nums1004200132

State

{ 100, 4, 200, 1, 3, 2 }

set

set size

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.

OPTIMAL Hash Set

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;
}

ALT 1 Brute force — sort, then scan runs

O(n log n) time · O(n) space

Sort the numbers, then sweep once counting the length of each run of consecutive integers, skipping duplicates and resetting whenever the gap breaks.

approach-2.ts
function longestConsecutive(nums: number[]): number {
  if (nums.length === 0) return 0;

  const sorted = [...nums].sort((a, b) => a - b);
  let best = 1;
  let cur = 1;

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) continue;        // duplicate — ignore
    if (sorted[i] === sorted[i - 1] + 1) cur++;        // extends the run
    else cur = 1;                                       // gap — restart
    best = Math.max(best, cur);
  }

  return best;
}

Note → Simple and correct, but the sort dominates at O(n log n). Dropping everything into a hash set and only starting a count at run-heads (values with no x − 1 present) reaches O(n).

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) required	Set for O(1) membership, skip non-starts
temptation to sort first	ask: 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 / 9

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?

QUESTION 08

#128 · Longest Consecutive SequenceFind 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.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Only start counting from sequence beginnings

RECIPE Build set, find starts, walk runs

COST Complexity & alternatives

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

RUN IT Only start from sequence beginnings — skip the middle

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Hash Set

ALT 1 Brute force — sort, then scan runs

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _