Longest Consecutive Sequence - Hash Set O(N)

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

Sequence elements can appear in any order in input; only value adjacency matters.

Example:
Input: [100,4,200,1,3,2]
Output: 4
Longest run is [1,2,3,4].

🎯 Real-World Analogy

Finding Street Number Streaks

Put all house numbers in a lookup table. Start counting only at addresses that do not have a predecessor (x-1). Then walk forward x+1, x+2 until streak ends.

💡 Key Insights

Hash set gives O(1) average membership checks.
Only start sequence expansion from true starts: numbers without predecessor.
Each number is visited in at most one forward expansion.
This avoids O(N log N) sorting and meets O(N) target.

💻 Solution Approaches

Approach 1: Sort + Scan

Time: O(N log N) | Space: O(1) extra (in-place sort variant)

Approach 2: Hash Set Starts (Recommended)

Time: O(N) average | Space: O(N)

Python Implementation

from typing import List


def longest_consecutive(nums: List[int]) -> int:
    values = set(nums)
    best = 0

    for x in values:
        if x - 1 in values:
            continue  # not a sequence start

        length = 1
        current = x
        while current + 1 in values:
            current += 1
            length += 1

        best = max(best, length)

    return best

JavaScript Implementation

function longestConsecutive(nums) {
  const values = new Set(nums);
  let best = 0;

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

    let current = x;
    let length = 1;

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

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

  return best;
}

🔍 Step-by-Step Walkthrough

For set {100,4,200,1,3,2}:

is start -> streak length 1
is start -> streak length 1
is start -> 2,3,4 found -> streak length 4
Maximum streak = 4

⚡ Complexity Analysis

Time: O(N) average. Each element participates in at most one forward chain walk.

Space: O(N) for hash set.

🔧 Edge Cases

Empty array -> 0
Single value -> 1
Duplicates should not inflate streak length
Negative numbers included in sequences
All disconnected numbers -> 1

🧪 Test Cases

Python

def test_longest_consecutive():
    assert longest_consecutive([100,4,200,1,3,2]) == 4
    assert longest_consecutive([0,3,7,2,5,8,4,6,0,1]) == 9
    assert longest_consecutive([]) == 0
    assert longest_consecutive([1,2,0,1]) == 3

    print("✅ all tests passed")

JavaScript

function testLongestConsecutive() {
  console.assert(longestConsecutive([100,4,200,1,3,2]) === 4, "test 1");
  console.assert(longestConsecutive([0,3,7,2,5,8,4,6,0,1]) === 9, "test 2");
  console.assert(longestConsecutive([]) === 0, "test 3");

  console.log("✅ all tests passed");
}

💼 Interview Tips

Call out why sorting misses O(N) target.
Explain "sequence start" trick; it is the key optimization.
Mention average-case O(1) hash lookups assumption.

🎓 Key Takeaways

Hash sets can replace sorting when adjacency by value matters.
Start-only expansion prevents redundant work.

← Back to All Algorithms