Skip to content

Volume ITechnology

4.4.9 — Longest Consecutive Sequence ​

LeetCode 128 · Medium · ★ Blind 75

The problem ​

You are given an unsorted list of whole numbers called nums. Find the length of the longest run of consecutive numbers that are all present in the list. Consecutive numbers are numbers that go up by exactly 1 each time, like 4, 5, 6, 7. They do not have to sit next to each other in the list. They only have to be present somewhere.

nums = [100, 4, 200, 1, 3, 2]          →  4    (the run 1, 2, 3, 4)
nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]  →  9    (the run 0 to 8)
nums = []                              →  0

The list has up to 100,000 numbers, each between minus one billion and one billion. The problem requires an O(n) solution. That rule is the real difficulty.

What the problem is really asking ​

If you sorted the list in your head, the runs would be easy to see. In [100, 4, 200, 1, 3, 2] sorted, you get 1, 2, 3, 4, 100, 200, and the run 1 to 4 jumps out.

But the problem forbids the time that sorting costs. So we must find the runs while only asking one kind of question: "is this number in the list?" For example, starting from 1, we ask "is 2 in the list? is 3? is 4? is 5?" and stop at the first "no".

A question of the form "is this in the list?" is a job for a hash set, which answers it in constant time.

The brute force, and where it wastes work ​

Sort, then count runs. This is a perfectly good first answer to say out loud.

python
def longestConsecutive(nums):
    if not nums:
        return 0
    nums = sorted(set(nums))          # remove repeats, then sort
    best = length = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:   # continues the run
            length += 1
            best = max(best, length)
        else:                             # the run is broken
            length = 1
    return best

set(nums) removes repeated numbers first. Without that, [1, 1, 2] would need a third case for "equal neighbours".

Sorting takes O(n \log n) time, which the problem rules out.

The waste in one sentence: sorting works out the exact order of every number, but we only need to know which numbers exist and whether the next number up exists.

The idea ​

Put every number into a set. Now "is n + 1 present?" costs constant time, and from any number we can walk forward along its run.

But if we walk from every number, we repeat work. In [1, 2, 3, 4] we would walk from 1 (4 steps), then from 2 (3 steps), then from 3 (2 steps), then from 4 (1 step). Every run gets walked again from each of its members. That is O(n^2) again.

The fix is one rule, and it is the whole algorithm:

Only start walking from a number that begins a run. A number n begins a run exactly when n - 1 is not in the set.

If n - 1 is in the set, then n sits in the middle of a run. That run will be walked from its true start anyway, so we skip n.

Think of tracing rivers on a map. If you dropped a boat in at every point along a river, you would trace the same water to the sea again and again. Instead, you only drop a boat at each river's source. A number is a "source" only if the number one below it is missing.

The solution ​

python
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)                     # (1)
        best = 0                          # (2)

        for n in s:                       # (3)
            if n - 1 in s:                # (4)
                continue
            length = 1                    # (5)
            while n + length in s:        # (6)
                length += 1
            best = max(best, length)      # (7)

        return best
ts
function longestConsecutive(nums: number[]): number {
  const s = new Set(nums);                // (1)
  let best = 0;                           // (2)

  for (const n of s) {                    // (3)
    if (s.has(n - 1)) continue;           // (4)
    let length = 1;                       // (5)
    while (s.has(n + length)) length++;   // (6)
    best = Math.max(best, length);        // (7)
  }

  return best;
}

Line by line ​

(1) s = set(nums). Put every number into a set. This does two jobs. It lets us ask "is this number present?" in constant time. And it removes repeats, so [1, 1, 2] correctly gives 2, not 3.

(2) best = 0. The longest run found so far. Starting at 0 means an empty list returns 0 without any special case.

(3) for n in s. Loop over the set, not the original list. If the list held the same number many times, looping over the list would visit it many times. The answer would still be right, but we would repeat the check in line (4) for every copy, and the speed argument below would no longer hold.

(4) The run-start check. If n - 1 is in the set, n is not the start of its run. We skip it with continue, which jumps straight to the next turn of the loop. This one line is what makes the solution fast.

(5) length = 1. We got past line (4), so n starts a run. The run contains at least n itself, so its length is at least 1.

(6) Walk forward. Is n + 1 present? If so, the length becomes 2. Then we check n + 2, and so on. We use n + length because, when the run so far has length numbers, the next number we need is exactly length steps above n. The loop stops at the first missing number.

(7) Keep the best. max(best, length) keeps whichever is larger: the best run found earlier, or this one.

Trace ​

Take nums = [100, 4, 200, 1, 3, 2]. The set is {1, 2, 3, 4, 100, 200}. A set has no fixed order, so the order below is just one possibility. The answer is the same in any order.

nIs n − 1 present?What happensSteps in the inner loopbest after
1no (0 missing)walk: 2 ✓, 3 ✓, 4 ✓, 5 ✗ → length 444
2yesskip04
3yesskip04
4yesskip04
100nowalk: 101 ✗ → length 114
200nowalk: 201 ✗ → length 114

The answer is 4. Count the inner-loop steps: 4 + 1 + 1 = 6. There are 6 distinct numbers. That is not a coincidence, as the next section shows.

Complexity, derived: why this is not O(n^2) ​

This is the reason the problem is asked. There is a while loop inside a for loop, and a loop inside a loop usually means n \times n work. Here it does not, and you must be able to explain why.

The mistake is to imagine the inner loop running for a long time on every turn of the outer loop. It cannot. Instead of counting the work per turn, count the total work over the whole program.

  1. The inner loop only runs when n starts a run, because of line (4).
  2. When it runs, it walks that one run from start to end, once.
  3. Every number belongs to exactly one run. Two runs that shared a number would join up into one run.
  4. So every number is stepped over by the inner loop at most once in the whole program.

That means the total work of the inner loop, added up over every turn, is at most the number of distinct values, which is at most n. The outer loop does a constant amount of work for each of at most n values. Building the set in line (1) touches each of the n numbers once.

So the total time is O(n) + O(n) + O(n) = O(n). The set holds up to n numbers, so the space is O(n).

This way of counting has a name: amortized analysis. "Amortized" means spreading a cost out. You charge each unit of work to one particular element, and then show that no element is ever charged twice. You will use the exact same argument three more times in this Part.

  • The sliding window in 4.6, where the left edge of the window only ever moves right.
  • The monotonic stack in 4.8, where each item is pushed once and popped at most once.
  • Manacher's algorithm in 4.31, where a centre point never moves backwards.

The mistake that quietly costs you the linear time ​

Delete line (4), and the code still returns the right answer. It just becomes O(n^2), because every run is walked again from each of its members.

No error appears, and every small example passes. Only the largest test times out. That is the dangerous kind of bug, because it looks like success until the input gets big.

Edge cases ​

  • An empty list. The loop never runs, and best stays 0.
  • All numbers the same, such as [7, 7, 7]. The set is {7}, the run is just 7, and the answer is 1.
  • Negative numbers and zero, such as [-1, 0, 1]. The set does arithmetic on numbers and does not care about their sign. The run starts at −1 because −2 is missing, and the answer is 3.
  • Huge gaps, such as [-1000000000, 1000000000]. Two runs of length 1.

The range of minus one billion to one billion matters in one way. It rules out a plain list of true/false flags indexed by value. That list would need two billion slots to hold at most a hundred thousand numbers. A set is the only sensible choice.

Variations you will meet ​

  • Union-find. Treat each number as a point, and join n to n + 1 whenever both exist. The answer is the size of the biggest joined group. It is more code here, but it shines when numbers arrive one at a time and you must answer between arrivals. 4.19.2 builds it.
  • Longest Consecutive Sequence in a Binary Tree. Same words, but a different problem. The run must follow parent-to-child links in a tree, so it is a tree walk, not a set problem. Do not mix them up.
  • Longest Harmonious Subsequence. Find the most numbers you can pick so that the biggest and smallest differ by exactly 1. Count each value, then for each value n, add its count to the count of n + 1. A single lookup per value, no walking.

The general lesson has two levels. The narrow one is: use a set to ask "is this present?", and walk each group only from its agreed starting point. The wider one is: do the work for each group only once, from one chosen member. The same guard appears as "only start a flood fill from a cell you have not visited yet" in 4.20.

What the interviewer will push on ​

"There is a loop inside a loop. Why is it not O(n^2)?" This gets asked here more than anywhere else in the group, because the code looks quadratic. Give the four-step argument above.

"Why check n - 1 and not n + 1?" You need one agreed starting point per run. The smallest number is a natural choice. Checking n + 1 instead finds the end of each run, and that also works if you then walk downwards.

"What if you had to return the run itself, not just its length?" Remember the starting number of the best run along with its length. The run is that number up to that number plus the length minus one.

"What if the numbers arrive one at a time?" The set solution needs the whole list first. Union-find handles arrivals, by joining each new number with its neighbours and keeping a running maximum.

One thing to volunteer: give the proof that the solution is linear before they ask. Explaining why your own speed claim is true is one of the clearest signals of real understanding.

Next: 4.5 Two Pointers. We drop the hash map and remove the nested loop a different way: two positions moving through one list, under a rule that proves neither ever needs to go back.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet