Topic: Learning notes

Longest Consecutive Sequence in TypeScript: Why the Set Scan Is Not O(n²)

Move from sorting to a Set, expand only sequence starts, and give a rigorous expected O(n) analysis for the longest consecutive sequence problem.

My first instinct was to deduplicate, sort, and scan. That produces the correct value, but sorting makes it O(n log n) when the problem asks for expected O(n). After reaching a Set solution with AI assistance, the important gap was not another code listing. It was explaining why a loop containing another while loop does not automatically become O(n²).

Problem

Given an unsorted collection of integers, return the length of its longest consecutive sequence. Count duplicates once, do not sort, and target expected O(n) time.

[100, 4, 200, 1, 3, 2, 2]
→ 4, because the longest sequence is [1, 2, 3, 4]

Why the sorting solution misses the constraint

Deduplicating, sorting, and comparing adjacent values is correct and easy to reason about. Its scan is O(n), but comparison sorting is conventionally analyzed as O(n log n), so the complete solution does not meet the requested bound.

That version is still a useful stepping stone because it defines what consecutive means. Once the interview question explicitly requires O(n), however, the solution needs membership lookup without a global ordering step.

The key: expand only from sequence starts

Put every number into a Set to remove duplicates. For each num, skip it when num - 1 exists because it cannot be the beginning of a sequence. Only a number without a predecessor starts a forward search for num + 1, num + 2, and so on.

In {1, 2, 3, 4}, only 1 enters the while loop. The other values are skipped because each has a predecessor. Starting from every value would instead walk lengths 4, 3, 2, and 1; one long sequence would then accumulate O(n²) work.

TypeScript solution

function longestConsecutive(nums: readonly number[]): number {
  const values = new Set(nums);
  let longest = 0;

  for (const num of values) {
    if (values.has(num - 1)) continue;

    let length = 1;
    while (values.has(num + length)) {
      length += 1;
    }

    longest = Math.max(longest, length);
  }

  return longest;
}

Why all of the inner loops still add up to linear work

The fact that length increases is not sufficient proof that each value is visited once. The real reason is that only sequence starts may enter the while loop. Every unique number belongs to exactly one consecutive sequence, and each sequence is expanded once from its minimum value.

The outer for examines each unique number once. Across the entire function, the inner loops also walk the numbers in those sequences only once. Under the common average-constant-time model for Set.has(), the expected time is O(n) and the additional space is O(n).

The JavaScript specification does not require Set to use a hash table or guarantee O(1) lookup. It requires average access to be sublinear and permits other implementations such as trees. Expected O(n) is therefore the standard hash-set model for this interview answer, not a universal worst-case engine guarantee.

Minimal verification

import assert from "node:assert/strict";

assert.strictEqual(longestConsecutive([100, 4, 200, 1, 3, 2, 2]), 4);
assert.strictEqual(longestConsecutive([0, -1, 1, 2, -2]), 5);
assert.strictEqual(longestConsecutive([]), 0);
assert.strictEqual(longestConsecutive([7, 7, 7]), 1);

These cases cover duplicates, negative values, an empty input, and a single unique value. They need no test framework, but still fail immediately if the core behavior regresses.

Common traps

• Sorting and returning the correct value while violating the expected O(n) constraint.
• Expanding from every number and degrading to O(n²) on one long sequence.
• Forgetting to deduplicate and counting or scanning repeated values again.
• Declaring every nested loop quadratic without summing how often elements actually enter the inner loop.
• Describing average constant-time Set.has() as a hard ECMAScript guarantee.

What I learned

• Constraints often point toward the data structure: when sorting is forbidden, efficient membership lookup is the obvious direction.
• Nested loops are not automatically quadratic; the total number of inner iterations is what matters.
• The num - 1 check is not a minor optimization. It is the reason the same sequence is not expanded repeatedly.
• An AI-assisted solution becomes useful only after I can explain its amortized analysis independently.

External references

• MDN: Set: documents uniqueness and the specification’s average sublinear access requirement.
• ECMAScript: Set Objects: defines the formal JavaScript Set semantics.
• Node.js: assert.strictEqual(): provides minimal executable checks for returned lengths.