Typorithm · medium

Longest Consecutive Sequence

longest-consecutive-sequencearrays-hashinghash-setsequence-startlinear

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Longest Consecutive Sequence

Arrays & Hashing

Put values in a Set and only extend runs from a true start (no predecessor) for overall O(n).

Sorting solves this in O(n log n), but a hash set reaches O(n).

The key trick is to start counting only at a value with no predecessor in the set.

Each run is then walked once upward, so every value is visited a constant number of times.

Start only when num-1 is absent.

Walk each run upward once.

Overall O(n).

function longestConsecutive(nums) {
  const set = new Set(nums);
  let longest = 0;

  for (const num of set) {
    if (!set.has(num - 1)) {
      let length = 1;

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

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

  return longest;
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Set for O(1) lookup

A Set gives constant-time membership and removes duplicates.

const set = new Set(nums)

2. Only at a start

A run begins where the predecessor is absent.

if (!set.has(num - 1))

3. Walk the run

Count consecutive values upward from the start.

while (set.has(num + length))

4. Track best

Keep the longest run found.

longest = Math.max(longest, length)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.