Longest Consecutive Sequence: the O(n) Hash Set Solution

Given an unsorted array nums, return the length of the longest run of consecutive integers that appear in it. The numbers need not be adjacent in the array, and duplicates do not lengthen a run.

For [100, 4, 200, 1, 3, 2] the answer is 4, from the run 1, 2, 3, 4.

Examples

Input	Output	Why
`nums = [100, 4, 200, 1, 3, 2]`	`4`	1, 2, 3, 4 are all present. 100 and 200 are islands.
`nums = [9, 1, 8, 2, 7, 3]`	`3`	1, 2, 3 is the longest. 7, 8, 9 is also length 3 — either is fine, the answer is the length.
`nums = [5, 5, 5]`	`1`	Duplicates do not extend a run.

Constraints

0 ≤ n ≤ 10⁵
−10⁹ ≤ nums[i] ≤ 10⁹
The array is not sorted
Values may repeat

Hints

Hint 1

Sorting works and costs O(n log n). Before you reach for it, ask what a sort actually buys you here — you never need the order, only whether a particular value is present.

Hint 2

Put everything in a hash set. Now "is x + 1 present?" is O(1). What is left is deciding where to start counting.

Hint 3

Only start counting at a value that begins a run — one whose predecessor is absent. That single test is what keeps the whole thing linear.

Dry run on `[100,4,200,1,3,2]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 8

Step 1 / 8

set
1000412002133425
best0
Everything goes into a set, so "is x present?" costs O(1). Duplicates disappear on the way in.
Step 2 / 8

set
1000412002133425
start100len1best1
100: 99 is absent, so 100 starts a run. Walk up while the next value is present — length 1. Best so far 1.
Step 3 / 8

set
1000412002133425
best1
4: 3 is in the set, so 4 is in the middle of a run. Skip it — it will be counted from its left end.
Step 4 / 8

set
1000412002133425
start200len1best1
200: 199 is absent, so 200 starts a run. Walk up while the next value is present — length 1. Best so far 1.
Step 5 / 8

set
1000412002133425
start1len4best4
1: 0 is absent, so 1 starts a run. Walk up while the next value is present — length 4. Best so far 4.
Step 6 / 8

set
1000412002133425
best4
3: 2 is in the set, so 3 is in the middle of a run. Skip it — it will be counted from its left end.
Step 7 / 8

set
1000412002133425
best4
2: 1 is in the set, so 2 is in the middle of a run. Skip it — it will be counted from its left end.
Step 8 / 8

set
1000412002133425
best4
No value is walked twice, because a walk only ever begins at a run's left end. Answer 4.

How to think about it

A set answers the only question you actually need: is this value present? Sorting answers a much harder question, and you pay O(n log n) for information you throw away.

So put every value in a hash set. For a value x, the run starting at x is x, x+1, x+2, … for as long as each is in the set. The naive version walks that chain from every element, which is O(n²) on an input like 1..n.

The fix is one line: only start walking when x - 1 is absent. That makes x the first element of its run, so every run is walked exactly once, from its left end. Across the whole array the walks visit each value at most once, so the total work is O(n) even though the code contains a loop inside a loop.

That argument — a nested loop that is linear because each element is entered by only one outer iteration — is worth being able to make out loud. It comes up whenever you amortise.

Complexity. Time O(n) · Space O(n)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def longest_run(nums):
    seen = set(nums)
    best = 0
    for x in seen:
        if x - 1 in seen:
            continue          # not the start of a run; it gets counted from its left end
        length = 1
        while x + length in seen:
            length += 1
        best = max(best, length)
    return best

#include <unordered_set>
#include <vector>
using namespace std;

int solve(vector<int> nums) {
    unordered_set<int> seen(nums.begin(), nums.end());
    int best = 0;
    for (int x : seen) {
        if (seen.count(x - 1)) continue;      // not the start of a run
        int length = 1;
        while (seen.count(x + length)) length++;
        if (length > best) best = length;
    }
    return best;
}

import java.util.*;

class Solution {
    public int longestRun(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) seen.add(x);
        int best = 0;
        for (int x : seen) {
            if (seen.contains(x - 1)) continue;   // not the start of a run
            int length = 1;
            while (seen.contains(x + length)) length++;
            if (length > best) best = length;
        }
        return best;
    }
}

function longestRun(nums) {
  const seen = new Set(nums);
  let best = 0;
  for (const x of seen) {
    if (seen.has(x - 1)) continue;   // not the start of a run
    let length = 1;
    while (seen.has(x + length)) length++;
    if (length > best) best = length;
  }
  return best;
}

use std::collections::HashSet;

fn solve(nums: &[i32]) -> i32 {
    let seen: HashSet<i32> = nums.iter().copied().collect();
    let mut best = 0;
    for &x in &seen {
        if seen.contains(&(x - 1)) { continue; }   // not the start of a run
        let mut length = 1;
        while seen.contains(&(x + length)) { length += 1; }
        if length > best { best = length; }
    }
    best
}

import qualified Data.Set as S

solve :: [Int] -> Int
solve xs = if S.null s then 0 else maximum (map runFrom starts)
  where
    s      = S.fromList xs
    starts = filter (\x -> not (S.member (x - 1) s)) (S.toList s)
    runFrom x = length (takeWhile (`S.member` s) [x ..])

Where people lose marks

Walking the chain from every element without the x - 1 check. It is still correct, but on [1, 2, …, n] it degrades to O(n²) and that is exactly the input an interviewer reaches for.
Forgetting that duplicates must not lengthen a run. Using a set rather than a list handles this for free; counting occurrences does not.
Returning 0 for a non-empty array. A single element is a run of length 1.
In C++ and Java, x + 1 on a value near the integer maximum overflows. The constraints here stay inside 32 bits, but say it out loud if asked.

Variants to try

Return the run itself rather than its length. (Keep the start value alongside the best length.)
What if the array does not fit in memory? (Sort externally and scan; the set no longer fits, so the O(n log n) solution wins.)
What if values arrive as a stream and you must answer at any moment? (Union–find, or a map from endpoint to run length that merges on insert.)

Next problems

Easy10 min

Longest run of consecutive integers

Examples

Constraints

Hints

Dry run on `[100,4,200,1,3,2]`

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in an unsorted array

The k most frequent values

Count subarrays with a given sum

Keep going

Pair with a given sum in an unsorted array

The k most frequent values

Count subarrays with a given sum

The pattern behind it

Longest run of consecutive integers

Examples

Constraints

Hints

Dry run on [100,4,200,1,3,2]

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in an unsorted array

The k most frequent values

Count subarrays with a given sum

Keep going

Pair with a given sum in an unsorted array

The k most frequent values

Count subarrays with a given sum

The pattern behind it

Dry run on `[100,4,200,1,3,2]`