Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesMathReviewsAbout
Language
EnglishTürkçe

Hashing

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 6
100
4
200
1
3
2

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

Longest consecutive run in O(n). Put every value in a set.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

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

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

Template connection

Hash-set membership plus “start a run only when x-1 is missing.”

Reflection