Longest Consecutive Sequence

MEDIUM✓ CHIP-TIMEDLC #128 — FULL STATEMENT

The briefingthe full drill, in my own words

The drill: Find the length of the longest run of consecutive integers hiding inside an unsorted array, without sorting it first.

An unsorted array of integers arrives, and hidden inside it somewhere is the longest unbroken run of consecutive values — the task is to report how long that run is.

The run doesn't need to appear in order inside the array itself; only that every integer from its lowest to its highest value exists somewhere in the array counts.

Sorting the array first would make runs easy to spot, but that already costs more than the target time budget allows — the drill is finding runs without ever ordering the input.

arrays can hold up to a few hundred thousand elements
values may be negative, zero, or positive, duplicates included
an empty array has a longest run of length zero
sorting the input is off the table as a solving technique

EX 01

nums = []

→ 0

empty array

EX 02

nums = [7]

→ 1

single element

EX 03

nums = [100, 4, 200, 1, 3, 2]

→ 4

run 1-2-3-4 scattered among outliers

The hintstake only what you need

HINT 1 THE NUDGE

Sorting makes consecutive runs trivial to spot in one scan, but sorting itself already costs more than linear time. What lets you find runs without an ordering step?

HINT 2 THE STRUCTURE

A hash set answers 'does this value exist' in O(1). Every run has exactly one true starting point: the value whose predecessor isn't in the set.

HINT 3 ONE STEP FROM THE ANSWER

For each value with no predecessor in the set, walk forward counting how far value+1, value+2, … stay present. Every number gets counted this way only once across the whole array.

Coach's boardthe pattern, step by step

RUN STARTS ONLYPATTERN · HASH SET, START POINTS ONLYnums = [100, 4, 200, 1, 3, 2]

100

200

VALUE SET

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

STEP 1

nums = [100, 4, 200, 1, 3, 2]. Drop everything into a set, then walk forward only from true run starts.

STEP 1 / 7 · ← → WORK TOO

The splitstwo paces, two languages

grind/longest-consecutive-sequence.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        values = set(nums)
        best = 0
        for x in values:
            if x - 1 not in values:  # only walk forward from a true run start
                length = 1
                while x + length in values:
                    length += 1
                best = max(best, length)
        return best

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 11 LN

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        ordered = sorted(set(nums))
        best = 1
        run = 1
        for i in range(1, len(ordered)):
            if ordered[i] == ordered[i - 1] + 1:
                run += 1
                best = max(best, run)
            else:
                run = 1
        return best

TIME O(N LOG N)SPACE O(N)PYTHON · TRAINING PACE · 14 LN

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> values = new HashSet<>();
        for (int x : nums) {
            values.add(x);
        }
        int best = 0;
        for (int x : values) {
            if (!values.contains(x - 1)) {
                int length = 1;
                while (values.contains(x + length)) {
                    length++;
                }
                best = Math.max(best, length);
            }
        }
        return best;
    }
}

TIME O(N)SPACE O(N)JAVA · RACE PACE · 19 LN

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        TreeSet<Integer> ordered = new TreeSet<>();
        for (int x : nums) {
            ordered.add(x);
        }
        int best = 1, run = 1;
        Integer prev = null;
        for (int x : ordered) {
            if (prev != null) {
                if (x == prev + 1) {
                    run++;
                    best = Math.max(best, run);
                } else {
                    run = 1;
                }
            }
            prev = x;
        }
        return best;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · TRAINING PACE · 25 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED