Free lesson · DSA Mastery - Interview Prep, End to End

Longest Consecutive Sequence

Medium6 min readdsahash-tables

Longest Consecutive Sequence

Longest Consecutive Sequence is one of the most elegant hash-set problems in the interview canon. The naive approaches - sort and scan, or check each number's neighbors - work but are O(n log n) or O(n²). The clever O(n) solution uses a single trick: only start counting from a sequence's beginning, which we can recognize in O(1) using a hash set.

This problem is a frequent ask at top companies because the O(n) solution requires a non-obvious insight. Candidates who reach for sorting first and only optimize later show they're thinking about correctness before performance - which is fine - but candidates who see the O(n) trick immediately demonstrate strong problem-solving intuition.

The Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input:  nums = [100, 4, 200, 1, 3, 2]
Output: 4

Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Length 4.

Example 2:

Input:  nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output: 9

Explanation: The longest sequence is [0, 1, 2, 3, 4, 5, 6, 7, 8]. Length 9.

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Approach

Naive O(n²) approach: For each number, count forward as long as the next number is in the set. The problem: starting from a middle of a sequence (say, 3 in [1, 2, 3, 4, 5]) does redundant work - we'll count from 3 to 5, then later count from 1 to 5, then from 2 to 5, etc.

Key insight: Only count from the beginning of a sequence. A number num is the beginning of a sequence iff num - 1 is NOT in the set. So we skip non-beginnings entirely.

This guarantees we count each sequence exactly once. The total work is O(n) because each element is visited at most twice: once as a "potential start" check, and once during the count loop of its own sequence.

graph TD
    A["Build hash set from nums"] --> B["For each num in set"]
    B --> C{"num - 1 in set?"}
    C -->|Yes| D["Skip (not a start)"]
    C -->|No| E["Count: while num + length in set, length++"]
    E --> F["Update max"]
    D --> G{"More?"}
    F --> G
    G -->|Yes| B
    G -->|No| H["Return max"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows the O(n) approach. We build a hash set of all nums. For each num, we check if num minus one is in the set - if so, num isn't a sequence beginning, skip it. Otherwise, count forward as long as consecutive values are in the set. Track the maximum length seen.

Why This Is O(n)

The check num - 1 in set is O(1). For each starting number, the inner loop runs as many iterations as the length of that specific sequence - and we count each sequence exactly once.

Total work: O(n) for set construction + O(sum of sequence lengths) for counting = O(n) total.

Code Implementation

public static int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) set.add(num);
    
    int max = 0;
    for (int num : set) {
        if (set.contains(num - 1)) continue;  // not a beginning
        
        int length = 1;
        while (set.contains(num + length)) {
            length++;
        }
        max = Math.max(max, length);
    }
    
    return max;
}

// Usage:
// System.out.println(longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));            // 4
// System.out.println(longestConsecutive(new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}));    // 9

This Java code implements Longest Consecutive Sequence in O(n) time. We build a hash set of all values. For each value in the set, we check if value minus one is also in the set - if yes, this isn't a sequence start, skip. Otherwise we count forward as long as consecutive values exist, tracking the maximum.

Iterating over the set (not the array) is important. The set is deduplicated, so we don't waste work processing duplicates. If the input had [1, 1, 1, 2], iterating the array would check the 1-as-start three times; iterating the set checks it once.

Walkthrough

Trace on nums = [100, 4, 200, 1, 3, 2].

Set: {1, 2, 3, 4, 100, 200}.

For num=100:
  100 - 1 = 99. 99 in set? No. 100 is a start.
  length = 1. 100 + 1 = 101 in set? No. Stop.
  max = 1.

For num=4:
  4 - 1 = 3. 3 in set? Yes. Not a start. Skip.

For num=200:
  199 in set? No. Start.
  201 in set? No. Stop. length = 1.
  max = 1.

For num=1:
  0 in set? No. Start.
  2 in set? Yes. length = 2.
  3 in set? Yes. length = 3.
  4 in set? Yes. length = 4.
  5 in set? No. Stop. length = 4.
  max = 4.

For num=3:
  2 in set? Yes. Skip.

For num=2:
  1 in set? Yes. Skip.

Return 4.

Result: 4. The sequence [1, 2, 3, 4] has length 4.

Note: only two of the six iterations actually do counting (100 and 1). The other four short-circuit at the "is this a start?" check.

Complexity Analysis

Why It Is O(n) Time

The outer loop iterates over distinct values (≤ n). For each value:

• The "is start?" check is O(1).
• If not a start, we move on (O(1) total work).
• If it is a start, the inner loop runs as many times as the length of that specific sequence.

Total inner loop work across all starts = total length of all sequences = at most n.

So total work is O(n) + O(n) = O(n).

Why Space Is O(n)

The hash set stores all unique values.

Variations & Follow-ups

What if duplicates should each be counted?

The problem treats "consecutive sequence" by value, not by index. Duplicates don't extend a sequence. Iterating over the set (which deduplicates) is correct.

What if you wanted the actual sequence, not just its length?

Track the start value alongside the max length:

int maxStart = 0, max = 0;
for (int num : set) {
    if (set.contains(num - 1)) continue;
    int length = 1;
    while (set.contains(num + length)) length++;
    if (length > max) {
        max = length;
        maxStart = num;
    }
}
// Sequence is [maxStart, maxStart + 1, ..., maxStart + max - 1].

What if numbers could be 64-bit?

Use Set<Long> instead of Set<Integer>. Same algorithm.

What if the data didn't fit in memory?

External hashing or sorting. The O(n) advantage disappears for disk-bound data.

What about negative numbers?

Hash sets handle negatives naturally. Algorithm works unchanged.

What about edge cases?

• Empty array: Set is empty. Loop doesn't execute. Returns 0.
• Single element: Set = {nums[0]}. One iteration, not a start (since nums[0] - 1 isn't in set - wait, yes it isn't, so it IS a start). length = 1. Returns 1.
• All duplicates of one value: Set has one element. Same as single element. Returns 1.
• All distinct, consecutive: One sequence of length n. Returns n.
• All distinct, no two consecutive: n singleton sequences. Returns 1.

Common Interview Pitfalls

• Iterating the array instead of the set. Duplicates cause repeated work. Performance can degrade.
• Forgetting the "is start?" check. Without it, the algorithm becomes O(n²) - each middle element counts forward, redoing work for the rest of its sequence.
• Sorting and scanning. O(n log n). Works but doesn't meet the O(n) requirement.
• Using a tree set instead of a hash set. Tree set has O(log n) operations. The algorithm becomes O(n log n).
• Manual cycle detection. Some candidates worry about infinite loops. The inner loop terminates when num + length isn't in the set - guaranteed to happen because the set is finite.

Why This Problem Matters

Longest Consecutive Sequence is the canonical example of set-based amortized counting. The pattern - "check if I'm at the start of a chain before traversing" - generalizes to many problems:

• Number of Islands (LeetCode #200) - count connected components by starting from unvisited cells.
• Connected components in general - DFS from unvisited nodes.
• Cycle detection in functional graphs - start traversal only from nodes not in any predecessor.
• Interval merging - process intervals only from the "left" boundary.

The trick of "skip if you're not the start" turns potentially-quadratic work into linear. Once you've seen it, you'll spot the same trick in many problems.

The next topic, Number of Matching Subsequences, applies hash-based bucketing to substring matching.

Back to DSA Mastery - Interview Prep, End to End