Mediumhashing

Longest Consecutive Sequence

Problem (restated)

Return the length of the longest consecutive elements sequence. Must run in O(n) time.

Intuition

Put numbers in a set. Only start counting from numbers that have no predecessor.

Approaches

Hash set starts only

Verified

Time O(n)Space O(n)

Idea. For each x with x-1 missing, count x, x+1, … until missing. Track max streak.

Walkthrough. [100,4,200,1,3,2] → start at 1 → 1..4 length 4.

Trade-offs. Sorting is simpler O(n log n) but fails the O(n) constraint.

Solution

export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;
    let y = x, len = 1;
    while (set.has(y + 1)) { y++; len++; }
    best = Math.max(best, len);
  }
  return best;
}

export function longestConsecutive(nums: number[]): number {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;
    let y = x, len = 1;
    while (set.has(y + 1)) { y++; len++; }
    best = Math.max(best, len);
  }
  return best;
}

Reflection

Which cue made you pick this pattern in under 90 seconds?
What input would break a wrong invariant?