128. Longest Consecutive Sequence

128

MediumArrays and HashingHash setSequence-start expansion

Longest Consecutive Sequence

Given an unsorted integer array nums, return the length of the longest run of consecutive integers (values differing by 1) that appear in the array. The algorithm must run in O(n) time.

Open official problem prompt ↗

In plain English

Measure the longest span of back-to-back integers present in the data, regardless of their order in the array.

Picture it like this

Guests wear numbered badges scattered around a room. To find the longest unbroken numeric line, you only bother forming a line starting from a guest whose number-minus-one is not in the room, then count how far the line stretches upward.

Example

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4
Why: The consecutive run 1, 2, 3, 4 has length 4; no longer run exists.

Constraints

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

Pattern lesson

See the pattern, then code

Sequence-start expansion

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Only start counting a run from a value that has no predecessor (x - 1 absent). From such a starter, walk upward as long as the next value exists; each element is visited at most twice overall.

New words, made simpleKnow these before the algorithm

Consecutive run: A set of integers with no gaps, like 5,6,7,8.
Run start: A value x for which x - 1 is not in the set, so no longer run can begin below it.
Amortized O(n): Though there is a nested loop, each element is entered by the inner walk at most once across the whole run.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort then scan

Simple but violates the O(n) requirement due to the sort.

Sort the array and count consecutive stretches linearly.

Time O(n log n)Space O(1) or O(n)

Best choiceSet with start-only expansion

Meets the linear-time bar; the start check is what prevents redundant walks.

Store all values in a set and expand upward only from run starts.

Time O(n)Space O(n)

The rule we keep true

Invariant

The inner while-loop is entered only for values x that are run starts (x - 1 absent), so every consecutive run is measured exactly once from its smallest element.

Why this is correct

Reasoning

Each run has a unique smallest element, and only that element passes the x - 1 absent test, so the run is counted once. The inner loop steps through the run's members, and across all runs those steps total at most n, giving linear time despite the nested loop.

The algorithm in three movesSay these aloud before coding

1Put all numbers in a set for O(1) membership

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

2For each value x, skip it unless x - 1 is absent (so x begins a run)

1 starts a run (0 absent) -> 1,2,3,4 length 4

3From a starter, count upward while x + length is present

100 and 200 are lone starters length 1

4Track the maximum run length found

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1000

2002

1 · Read99 in set?

2 · AskIs 100 a run start?

3 · Update staterun 100 only

4 · Resultlength 1, longest = 1

Key takeaway

1 has no predecessor 0, so the walk 1->2->3->4 measures the longest run.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Build the set
Deduplicates and enables O(1) membership tests.
2
Lines 5-6Start filter
The x - 1 not in set check ensures we only expand from the base of each run, which is what keeps the work linear.
3
Lines 7-10Expand and record
Walk upward while the next value exists, then update the best length.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty array returns 0
Duplicates like [1,1,2] — the set collapses them, run length is 2
All identical values give length 1
Single element gives length 1

Common beginner mistakes

Omitting the run-start check, which turns the nested loop into O(n^2) by re-walking runs from every member
Iterating over nums instead of the set, redoing work for duplicates
Forgetting to handle the empty input, leaving longest at 0 (correct here) but crashing if you seed with nums[0]

Check your understanding

The code has a while-loop inside a for-loop; why is it still O(n) overall?

Longest Consecutive Sequence

Longest Consecutive Sequence

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing