Longest Consecutive Sequence (LeetCode 128)
You get an integer array nums, in no particular order. A run is a chain of whole numbers that each exceed the one before by exactly 1 (x, x + 1, x + 2, ...). Find the longest run whose values all appear somewhere in nums, at any positions, and return how many values it holds.
Your algorithm has to finish in O(n) time.
Worked Examples
nums = [100,4,200,1,3,2]4[1, 2, 3, 4] holds 4 values.nums = [0,3,7,2,5,8,4,6,0,1]9nums = [1,0,1,2]3⚖️Formal Constraints & Bounds
0 <= nums.length <= 105-109 <= nums[i] <= 109
Core Insight
A run has exactly one value whose predecessor is missing from the set, so testing x - 1 in seen finds every run's start in , and only a start is ever walked upward -- which is what keeps the whole scan linear.
Real-World Scenario & Production Applications
Compacting a set of IDs into ranges works the same way: free port numbers, allocated row IDs, or reserved seat numbers, collected in any order, fold into [start, end] blocks by the same test -- a value only opens a new block when the value one below it is not in the set.
Step-by-Step Execution Trace Table
Input nums = [100,4,200,1,3,2] (LeetCode Example 1, delta = 1). seen = {100,4,200,1,3,2}:
| Step | left | left - delta in seen? | Action | length reached | best after the step |
|---|---|---|---|---|---|
| 1 | 100 | No (99 absent) | Run start: walk 101 -- absent, stop | 1 | 1 |
| 2 | 4 | Yes (3 present) | Not a start: skip | -- | 1 |
| 3 | 200 | No (199 absent) | Run start: walk 201 -- absent, stop | 1 | 1 |
| 4 | 1 | No (0 absent) | Run start: walk 2✓, 3✓, 4✓, 5 absent, stop | 4 | 4 |
| 5 | 3 | Yes (2 present) | Not a start: skip | -- | 4 |
| 6 | 2 | Yes (1 present) | Not a start: skip | -- | 4 |
| End | return 4: the run [1, 2, 3, 4] |
| 1 | A run of consecutive values has exactly one start: the value whose predecessor (`x - 1`) does not appear anywhere in the array. |
| 2 | Put every value into a hash set once; for each value, check whether it is a run's start before doing any more work for it. |
| 3 | `seen = set(nums)`; `for x in seen: if x - 1 in seen: continue` (skip anything that is not a start); otherwise `length = 1; while x + length in seen: length += 1`; track `best = max(best, length)`. |
| 4 | The trap: skipping the `x - 1 in seen` check and walking from every value makes the scan $O(N^2)$ on one long run -- the pruning check is what keeps every value visited by at most one walk. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash set answers one question in one step: "is this value here?" Finding the longest run of consecutive numbers in an unsorted array looks like it needs sorting first, but sorting spends just to learn an ordering the problem never asks you to keep -- it only asks for the length of the longest run. A hash set gives the same "what comes next?" answer in , so the real problem is not finding runs, it is finding run starts: a value is a start exactly when nothing one smaller than it exists, and once you are standing at a start, walking forward one step at a time with set lookups costs nothing extra because each value is only ever walked past once.
🏟️ The Analogy: Train Cars on a Siding, Found Out of Order
Picture rail cars numbered 1 through 9, uncoupled and shunted onto a siding in random order: car 4, then 100, then 1, then 3, then 2. A yard worker checking every car against every other car to find the longest coupled chain would take forever. Instead, she keeps a clipboard of every car number present (the hash set), and for each car asks one question: "is the car numbered one less than this one on my list?" If yes, this car is the middle or end of some chain and someone else will walk it from its front; skip it. If no, this car is a chain's front, so walk forward from it, car by car, counting how many are coupled before the chain breaks. Every car is asked "am I a front?" once, and every car is counted by a walk at most once, no matter how the cars were shunted onto the siding.
🔑 Why It Works
A run of consecutive values has exactly one smallest member, and that member is the only one in the run whose predecessor is missing from seen. So if x - 1 in seen: continue identifies, in , every value that is not a run's start, and the while loop only ever fires for the one value per run that is. Across the whole array, the for loop costs lookups and the combined while loops cost at most more lookups, since each value is walked past by at most one run -- the one it belongs to.
Skipping the pruning check: walking the upward probe from every value, not only from values whose predecessor is absent, re-walks every run once per value inside it -- O(N^2) on one long run, which the problem's
O(n)requirement forbids.Not collapsing duplicates: iterating
numsdirectly instead ofset(nums)lets a repeated value either inflatelengthor waste work re-starting a walk already counted;set(nums)fixes both.Forgetting the empty-array case:
nums = []must return0; the explicitif not nums: return 0guard makes this read as a deliberate check rather than an accident of the loop never running.Re-deriving the run going downward instead of upward: walking both
x - 1andx + 1from every value without the pruning test double-counts the same run from each of its members; the pruning check is what makes a single-direction (upward-only) walk sufficient.Assuming sorted input:
numsis explicitly unsorted and the algorithm never sorts it; there is no step that depends on the array's original order, only on set membership.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Unsorted array" plus "must run in O(n) time" rules out sorting; "longest run of consecutive values" is a question about relative adjacency (x, x + 1, x + 2, ...), not array order or index adjacency -- the Hash-Set Sequence Scanning model.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
A run is walked only from its start, the one value in it whose predecessor (left - delta) is absent from seen; every other value in the array is pruned in by that same check.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
seen = set(nums): duplicates must collapse first, or[5, 5, 5]could be mistaken for a run of length 3 instead of 1.nums = []: handled explicitly byif not nums: return 0-- without it,seenwould still be empty andbestwould still correctly stay0, but the guard makes the empty case read as intentional rather than incidental.nums[i]can be negative:left - delta in seenandleft + length * delta in seenboth work unchanged, since Python'sinmakes no assumption about sign.deltamust be a positive integer: the start-boundary guard and the upward walk both assumedelta >= 1;delta = 0makes every value its own predecessor anddelta < 0reverses which end of a run is the "head".
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Hash-Set Sequence Scanning. Sorting would find the runs in
O(N log N), but the problem demandsO(N), so instead I put every value into a hash set, which also collapses duplicates. For each value, I ask one question: is its predecessor (left - delta,delta = 1here) in the set? If yes, it is the middle or end of some run, and whichever value starts that run will walk through it on its own, so I skip it inO(1). If no, it is a run's start, so only then do I walk forward onedeltaat a time, counting the length. The reason this is stillO(N)and not O(N^2) is that every value is walked past by at most one run's upward walk, the one it belongs to, so the total number of lookups across every walk, plus the one lookup per value in the outer loop, is at most2N. I keep the best length seen across every start. The same code solves the general "longest arithmetic run with common differencedelta" problem; LC 128 is just thedelta = 1case.
Complexity & Mathematical Proof
O(N)
Look at the code: seen = set(nums) is one pass over nums, time and space for the set (duplicates collapse to one entry each, so the set holds at most distinct values). for left in seen runs once per distinct value. Inside, if left - delta in seen is one average hash lookup. The while left + length * delta in seen loop only executes for values that pass the pruning check -- the start of each run -- and across every run it executes, it never revisits a value: once length has walked past a value, no other left in the outer loop reaches that value with a while loop of its own, because that value's own pruning check (left - delta in seen) was true. So every distinct value is touched by at most one for-loop iteration's own check plus at most one while-loop step, total work at most 2N hash lookups, , for any fixed delta.
O(N)
Look at the code: seen = set(nums) is one pass over nums, time and space for the set (duplicates collapse to one entry each, so the set holds at most distinct values).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "unsorted array", "must run in O(n) time". Sorting is ruled out, and the question is "is the next value present?": a Hash Map (here a set) answers it in one lookup.
, values in . Sorting costs and is not allowed; a counting array over values is impossible. Budget: time, space.
Walking up from every value, not only from starts, is on one long run. Duplicates must not break a run ([1,0,1,2] is 3). An empty array returns 0.
Core Algorithmic State Invariants
- Only a Value Whose Predecessor Is Missing Starts a Walk
seen = set(nums) holds every value once. if x - 1 in seen: continue skips every value that is not the smallest member of its run, so the while loop only ever walks upward from a run's one true start.
- Every Value Is Visited by at Most One Walk
A value that is skipped by the start check is still counted, later, by the while loop of the run's real start. So the for loop's N checks plus the combined while loops' lookups never exceed 2N in total, which is what keeps the whole scan O(N).
Longest Consecutive Sequence (LeetCode 128)
You get an integer array nums, in no particular order. A run is a chain of whole numbers that each exceed the one before by exactly 1 (x, x + 1, x + 2, ...). Find the longest run whose values all appear somewhere in nums, at any positions, and return how many values it holds.
Your algorithm has to finish in O(n) time.
Worked Examples
nums = [100,4,200,1,3,2]4[1, 2, 3, 4] holds 4 values.nums = [0,3,7,2,5,8,4,6,0,1]9nums = [1,0,1,2]3⚖️Formal Constraints & Bounds
0 <= nums.length <= 105-109 <= nums[i] <= 109
Core Insight
A run has exactly one value whose predecessor is missing from the set, so testing x - 1 in seen finds every run's start in , and only a start is ever walked upward -- which is what keeps the whole scan linear.
Real-World Scenario & Production Applications
Compacting a set of IDs into ranges works the same way: free port numbers, allocated row IDs, or reserved seat numbers, collected in any order, fold into [start, end] blocks by the same test -- a value only opens a new block when the value one below it is not in the set.
Step-by-Step Execution Trace Table
Input nums = [100,4,200,1,3,2] (LeetCode Example 1, delta = 1). seen = {100,4,200,1,3,2}:
| Step | left | left - delta in seen? | Action | length reached | best after the step |
|---|---|---|---|---|---|
| 1 | 100 | No (99 absent) | Run start: walk 101 -- absent, stop | 1 | 1 |
| 2 | 4 | Yes (3 present) | Not a start: skip | -- | 1 |
| 3 | 200 | No (199 absent) | Run start: walk 201 -- absent, stop | 1 | 1 |
| 4 | 1 | No (0 absent) | Run start: walk 2✓, 3✓, 4✓, 5 absent, stop | 4 | 4 |
| 5 | 3 | Yes (2 present) | Not a start: skip | -- | 4 |
| 6 | 2 | Yes (1 present) | Not a start: skip | -- | 4 |
| End | return 4: the run [1, 2, 3, 4] |
| 1 | A run of consecutive values has exactly one start: the value whose predecessor (`x - 1`) does not appear anywhere in the array. |
| 2 | Put every value into a hash set once; for each value, check whether it is a run's start before doing any more work for it. |
| 3 | `seen = set(nums)`; `for x in seen: if x - 1 in seen: continue` (skip anything that is not a start); otherwise `length = 1; while x + length in seen: length += 1`; track `best = max(best, length)`. |
| 4 | The trap: skipping the `x - 1 in seen` check and walking from every value makes the scan $O(N^2)$ on one long run -- the pruning check is what keeps every value visited by at most one walk. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
A hash set answers one question in one step: "is this value here?" Finding the longest run of consecutive numbers in an unsorted array looks like it needs sorting first, but sorting spends just to learn an ordering the problem never asks you to keep -- it only asks for the length of the longest run. A hash set gives the same "what comes next?" answer in , so the real problem is not finding runs, it is finding run starts: a value is a start exactly when nothing one smaller than it exists, and once you are standing at a start, walking forward one step at a time with set lookups costs nothing extra because each value is only ever walked past once.
🏟️ The Analogy: Train Cars on a Siding, Found Out of Order
Picture rail cars numbered 1 through 9, uncoupled and shunted onto a siding in random order: car 4, then 100, then 1, then 3, then 2. A yard worker checking every car against every other car to find the longest coupled chain would take forever. Instead, she keeps a clipboard of every car number present (the hash set), and for each car asks one question: "is the car numbered one less than this one on my list?" If yes, this car is the middle or end of some chain and someone else will walk it from its front; skip it. If no, this car is a chain's front, so walk forward from it, car by car, counting how many are coupled before the chain breaks. Every car is asked "am I a front?" once, and every car is counted by a walk at most once, no matter how the cars were shunted onto the siding.
🔑 Why It Works
A run of consecutive values has exactly one smallest member, and that member is the only one in the run whose predecessor is missing from seen. So if x - 1 in seen: continue identifies, in , every value that is not a run's start, and the while loop only ever fires for the one value per run that is. Across the whole array, the for loop costs lookups and the combined while loops cost at most more lookups, since each value is walked past by at most one run -- the one it belongs to.
Skipping the pruning check: walking the upward probe from every value, not only from values whose predecessor is absent, re-walks every run once per value inside it -- O(N^2) on one long run, which the problem's
O(n)requirement forbids.Not collapsing duplicates: iterating
numsdirectly instead ofset(nums)lets a repeated value either inflatelengthor waste work re-starting a walk already counted;set(nums)fixes both.Forgetting the empty-array case:
nums = []must return0; the explicitif not nums: return 0guard makes this read as a deliberate check rather than an accident of the loop never running.Re-deriving the run going downward instead of upward: walking both
x - 1andx + 1from every value without the pruning test double-counts the same run from each of its members; the pruning check is what makes a single-direction (upward-only) walk sufficient.Assuming sorted input:
numsis explicitly unsorted and the algorithm never sorts it; there is no step that depends on the array's original order, only on set membership.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Unsorted array" plus "must run in O(n) time" rules out sorting; "longest run of consecutive values" is a question about relative adjacency (x, x + 1, x + 2, ...), not array order or index adjacency -- the Hash-Set Sequence Scanning model.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
A run is walked only from its start, the one value in it whose predecessor (left - delta) is absent from seen; every other value in the array is pruned in by that same check.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
seen = set(nums): duplicates must collapse first, or[5, 5, 5]could be mistaken for a run of length 3 instead of 1.nums = []: handled explicitly byif not nums: return 0-- without it,seenwould still be empty andbestwould still correctly stay0, but the guard makes the empty case read as intentional rather than incidental.nums[i]can be negative:left - delta in seenandleft + length * delta in seenboth work unchanged, since Python'sinmakes no assumption about sign.deltamust be a positive integer: the start-boundary guard and the upward walk both assumedelta >= 1;delta = 0makes every value its own predecessor anddelta < 0reverses which end of a run is the "head".
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Hash-Set Sequence Scanning. Sorting would find the runs in
O(N log N), but the problem demandsO(N), so instead I put every value into a hash set, which also collapses duplicates. For each value, I ask one question: is its predecessor (left - delta,delta = 1here) in the set? If yes, it is the middle or end of some run, and whichever value starts that run will walk through it on its own, so I skip it inO(1). If no, it is a run's start, so only then do I walk forward onedeltaat a time, counting the length. The reason this is stillO(N)and not O(N^2) is that every value is walked past by at most one run's upward walk, the one it belongs to, so the total number of lookups across every walk, plus the one lookup per value in the outer loop, is at most2N. I keep the best length seen across every start. The same code solves the general "longest arithmetic run with common differencedelta" problem; LC 128 is just thedelta = 1case.
Complexity & Mathematical Proof
O(N)
Look at the code: seen = set(nums) is one pass over nums, time and space for the set (duplicates collapse to one entry each, so the set holds at most distinct values). for left in seen runs once per distinct value. Inside, if left - delta in seen is one average hash lookup. The while left + length * delta in seen loop only executes for values that pass the pruning check -- the start of each run -- and across every run it executes, it never revisits a value: once length has walked past a value, no other left in the outer loop reaches that value with a while loop of its own, because that value's own pruning check (left - delta in seen) was true. So every distinct value is touched by at most one for-loop iteration's own check plus at most one while-loop step, total work at most 2N hash lookups, , for any fixed delta.
O(N)
Look at the code: seen = set(nums) is one pass over nums, time and space for the set (duplicates collapse to one entry each, so the set holds at most distinct values).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "unsorted array", "must run in O(n) time". Sorting is ruled out, and the question is "is the next value present?": a Hash Map (here a set) answers it in one lookup.
, values in . Sorting costs and is not allowed; a counting array over values is impossible. Budget: time, space.
Walking up from every value, not only from starts, is on one long run. Duplicates must not break a run ([1,0,1,2] is 3). An empty array returns 0.
Core Algorithmic State Invariants
- Only a Value Whose Predecessor Is Missing Starts a Walk
seen = set(nums) holds every value once. if x - 1 in seen: continue skips every value that is not the smallest member of its run, so the while loop only ever walks upward from a run's one true start.
- Every Value Is Visited by at Most One Walk
A value that is skipped by the start check is still counted, later, by the while loop of the run's real start. So the for loop's N checks plus the combined while loops' lookups never exceed 2N in total, which is what keeps the whole scan O(N).