2Brute2Best
🔥0

Longest Consecutive Sequence

Medium·LeetCode #128 Pro OnlyMedium
LeetCode
01

Problem Statement

You are given an unsorted integer array nums.

Pick some of its values that form a run of consecutive integers — like 4, 5, 6, 7 — and return the length of the longest such run. The values can be anywhere in the array and in any order; only the values matter, not their positions.

Your algorithm must run in O(N) time.

Input

An integer array nums (it can be empty and can contain duplicates).

Output

The length of the longest run of consecutive values present in nums.

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

The values 1, 2, 3, 4 are all present. They are scattered in the array, but that does not matter.

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

The values 0 through 8 are all present. The second 0 does not make the run longer.

Example 3
Input: nums = [1, 0, 1, 2]
Output: 3

The run is 0, 1, 2.

Constraints
  • • 0 ≤ nums.length ≤ 10^5
  • • −10^9 ≤ nums[i] ≤ 10^9
  • • Must run in O(N) time.
02

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“consecutive elements sequence”
→ Consecutive in **value** (x, x + 1, x + 2), not neighbours in the array.
“unsorted array”
→ Order is useless, so sorting or a set are the two tools.
“must run in O(N)”
→ Sorting is ruled out → hash set with O(1) lookups.
“longest”
→ Measure each run once and keep the maximum.
03

Approach Complexity Ladder

Brute Force — grow a run from every elementO(N³)O(1)

From each x, search the array for x + 1, x + 2, …

Better — sort, then scanO(N log N)O(1)

Sort; consecutive values become a stretch of the array

Optimal — hash set, start only at run beginningsO(N)O(N)

Count up from x only when x − 1 is not in the set

Brute Force Intuition

Treat every element x as a possible start. Search the whole array for x + 1; if found, search for x + 2, and so on. The longest chain found is the answer.

Recognition rule for this sub-pattern:

Put everything in a set first; then each "is X present?" check is O(1). Start work only from the beginning of a run.
Remember this · Arrays & Hashing
Trigger
"Have I seen X before?", pairs that add up to a target, grouping things that look alike, counting occurrences.
Think
Instead of scanning again for each element, can I remember earlier elements in a map?
Key question
What exactly do I store as the key, and what as the value?
Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms
Interactive step-by-step playback with pointer & array state transitions
52 comprehensive LLD chapters
Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions
40 C++ basics labs & hardware memory models
Vtables, byte layouts, assembly insights, and multi-threading race conditions
Production-ready C++23 source code
Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways
Create Free AccountLog in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track
C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track
Contains DuplicateFirst Missing Positive