FAANG · LeetCode #128

Longest Consecutive Sequence — three-stage drill

1The ProblemMedium

Longest Consecutive Sequence

Length of the longest run of consecutive integers, in O(n).

Examples

[100,4,200,1,3,2]→ 4[0,3,7,2,5,8,4,6,0,1]→ 9

constraintUnsorted; must run in O(n) — so sorting is off the table.

2The PatternTIME O(n) · SPACE O(n)

Arrays & Hashing

Trade space for time: a hash map turns 'have I seen this?' into an O(1) lookup.

Problems using this pattern

3The SolutionRESULT → 4

Step through it

100 → is 99 in the set? no → a run starts here · count 100… → length 1

Step 1 / 7

Python▎only count from a run's start

1def longestConsecutive(nums):
2    s = set(nums)
3    best = 0
4    for x in s:
5        if x - 1 not in s:        # x starts a run
6            length = 1
7            while x + length in s:
8                length += 1
9            best = max(best, length)
10    return best

why it worksSorting would give O(n log n). Instead drop everything into a hash set, then only start counting a run at a value whose predecessor (x − 1) is ABSENT — that's the true start of a sequence. From there, walk x+1, x+2, … by O(1) set lookups. Each value is visited at most twice, so the whole thing is O(n).

Arrow keys to navigate · escape to reset

All problems by pattern

Two Pointers

Sliding Window

Prefix Sum

Monotonic Deque

Shortest Subarray with Sum at Least K

Binary Search

Arrays & Hashing

Monotonic Stack

Intervals

Longest Consecutive Sequence — three-stage drill