Skip to content
16-Week DSA Roadmap
LeetCode #128MediumProblem 8 of 8

Longest Consecutive Sequence

Find the length of the longest run of consecutive whole numbers hidden in an unsorted array.

  • Find the start of a sequence
  • Hash set membership

Before this, know: Hash sets (Set in JavaScript, set in Python), While loops

The problem in plain English

You get an unsorted array of whole numbers, nums. A consecutive sequence is a run of numbers that each go up by exactly 1, like 1, 2, 3, 4. The numbers can be anywhere in the array, in any order. Return the length of the longest such run.

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

nums
  1. 1000
  2. 41
  3. 2002
  4. 13
  5. 34
  6. 25
number line
  1. 1
  2. 2
  3. 3
  4. 4
  5. 100
  6. 200
Placed on a number line, the values form three runs: 1–4 (length 4), 100 (length 1) and 200 (length 1). The answer is 4.

The rules that matter:

  • Only the values matter, not where they sit in the array.
  • Duplicates don’t extend a run: [1, 2, 2, 3] has a longest run of 3 (1, 2, 3).
  • An empty array has answer 0. Numbers can be negative.
  • The problem demands O(n) time, which rules out sorting (O(n log n)). (Big-O notation is a short way of saying how the work grows as the input grows: O(n) means “double the array, double the work”, and sorting grows a bit faster than that. See Big-O in 5 minutes.)

Before you code: think it through

So two questions matter for each number x:

  1. Is x the start of a run? That’s true exactly when x − 1 is not in the array.
  2. If it is, how long is the run? Keep asking “is x + 1 here? x + 2?” until the answer is no.

Both are “is this value here?” questions, which a hash set answers in about one step. (A hash set is a collection that remembers values and can say whether a value is in it almost instantly; Set in JavaScript, set in Python.)

Pause and think

nums = [100, 4, 200, 1, 3, 2]. Which of these numbers are starts of a run? Which are not?

Approach 1: Brute force

From every number, count upward: is num + 1 in the array? num + 2? Each question scans the whole array (includes in JS, in on a list in Python).

Brute force: count up from every number

nums = [100, 4, 200, 1, 3, 2]

nums
  1. 1000
  2. 41
  3. 2002
  4. 13
  5. 34
  6. 25
variables
looking for
101
length
1
best
0
cells read
6
  • Starting number
  • Found by the scan

From 100: scan the whole array for 101. Not there, so this streak has length 1. (6 cells read so far.)

Step 1 / 19

Which line is running?

function longestConsecutive(nums) {  let best = 0;  for (const num of nums) {    let length = 1;Running now:     while (nums.includes(num + length)) { // scans the whole array      length++;    }    best = Math.max(best, length);  }  return best;}

Brute force: count up from every number

function longestConsecutive(nums) {  let best = 0;  for (const num of nums) {    let length = 1;    while (nums.includes(num + length)) { // scans the whole array      length++;    }    best = Math.max(best, length);  }  return best;}
def longest_consecutive(nums):    best = 0    for num in nums:        length = 1        while num + length in nums:  # scans the whole list            length += 1        best = max(best, length)    return best

Why is it slow?

Two kinds of waste pile up:

  1. Every search scans the array. “Is 5 in the array?” reads up to n cells.
  2. We recount the same runs. For the run 1, 2, 3, 4 we count from 1 (4 long), then from 2 (3 long), from 3, and from 4. That’s 4 + 3 + 2 + 1 = 10 searches for one run.

If the whole array is one long run of n numbers, we do about n × n ÷ 2 searches, each reading up to n cells: O(n³). For 1,000 numbers that’s hundreds of millions of reads.

A middle ground: sort first

Sort the numbers, then walk through them: if a number is exactly 1 more than the previous one, the run grows; if it’s equal, skip it (duplicate); otherwise the run restarts at 1.

Sort, then walk

function longestConsecutive(nums) {  if (nums.length === 0) return 0;  const s = [...nums].sort((a, b) => a - b);  let best = 1;  let length = 1;  for (let i = 1; i < s.length; i++) {    if (s[i] === s[i - 1]) continue; // duplicate: streak unchanged    length = s[i] === s[i - 1] + 1 ? length + 1 : 1;    best = Math.max(best, length);  }  return best;}
def longest_consecutive(nums):    if not nums:        return 0    s = sorted(nums)    best = length = 1    for i in range(1, len(s)):        if s[i] == s[i - 1]:            continue  # duplicate: streak unchanged        length = length + 1 if s[i] == s[i - 1] + 1 else 1        best = max(best, length)    return best

That’s O(n log n), a perfectly good answer in practice. But the problem asks for O(n), so we need to drop the sort.

The pattern: find the start of a sequence

Fix the first waste with a hash set (each search becomes one step). Fix the second waste with one extra question.

Pattern

Find the start of a sequence

Template

Use it when: you need runs or chains of related values (x, x + 1, x + 2…) in unsorted data, in O(n).

Signal words

  • “consecutive”
  • “longest sequence”
  • “unsorted”
  • “O(n) time”
  • “chain of”

Approach 2: Hash set, count only from starts

  1. Put all the numbers in a hash set. Duplicates disappear.
  2. Set best = 0.
  3. For each number num in the set: if num − 1 is in the set, skip it. It’s in the middle of a run.
  4. Otherwise num starts a run. Set length = 1, and while num + length is in the set, add 1 to length.
  5. Update best with the bigger of best and length.
  6. Return best.

Press Play. The top row is the set in the order the loop visits it; the number line below shows the values in order with gaps marked “…”. Watch the non-starts fade out after a single lookup, and watch each start sweep along its run. Keep an eye on the lookups counter.

Hash set, count only from starts

nums = [100, 4, 200, 1, 3, 2]

the set, in loop order
  1. 1000
  2. 41
  3. 2002
  4. 13
  5. 34
  6. 25
number line
  1. 1
  2. 2
  3. 3
  4. 4
  5. 100
  6. 200
variables
length
—
best
0
lookups
0for 6 numbers
  • Number we're looking at
  • Not a start (skipped)
  • Streak being counted
  • Lookup found
  • Lookup not found
  • Longest streak

Put every number into a hash set: 6 distinct numbers. Now "is x in the set?" takes about one step. The number line below shows them in order, with … where numbers are missing.

Step 1 / 17

Which line is running?

function longestConsecutive(nums) {Running now:   const set = new Set(nums); // instant "is x here?" and no duplicates  let best = 0;  for (const num of set) {    if (set.has(num - 1)) continue; // not a start: num - 1 will count it    let length = 1;    while (set.has(num + length)) {      length++;    }    best = Math.max(best, length);  }  return best;}

Why is this O(n), with a loop inside a loop?

A while inside a for usually means O(n²). Here it doesn’t, and this is the question interviewers love. Count the work per number instead of per loop:

  • Every number gets one “is num − 1 here?” lookup in the for loop. That’s n lookups.
  • The while loop only runs from a start, and it walks forward through that start’s own run. Runs don’t overlap, so every number is stepped on by the while loop at most once in total, plus one failed lookup at the end of each run.

So the total is at most about n + n + n = 3n lookups: O(n). In “Example 2” there are 9 distinct numbers and the counter ends at 18. Without the start check, the run 0…8 would be counted from 0, then from 1, then from 2…: 9 + 8 + … + 1 = 45 steps instead.

The code, line by line

Hash set, count only from starts

function longestConsecutive(nums) {  const set = new Set(nums); // instant "is x here?" and no duplicates  let best = 0;  for (const num of set) {    if (set.has(num - 1)) continue; // not a start: num - 1 will count it    let length = 1;    while (set.has(num + length)) {      length++;    }    best = Math.max(best, length);  }  return best;}
def longest_consecutive(nums):    num_set = set(nums)  # instant "is x here?" and no duplicates    best = 0    for num in num_set:        if num - 1 in num_set:            continue  # not a start: num - 1 will count it        length = 1        while num + length in num_set:            length += 1        best = max(best, length)    return best

Python puts the “skip” check on two lines (5–6), so from there on its line numbers run one ahead of JavaScript’s.

  • Line 1: define the function. (LeetCode: var longestConsecutive = function(nums) in JS, def longestConsecutive(self, nums) in class Solution in Python.)
  • Line 2: build the set from the whole array in one go. new Set(nums) / set(nums). Duplicates disappear, which is exactly what we want.
  • Line 3: best starts at 0, the right answer for an empty array.
  • Line 4: loop over the set, not over nums. If nums contained the same start many times (like 100,000 copies of 1), looping over nums would recount that run every time.
  • Line 5 (JS) / lines 5–6 (Python): if num − 1 is present, num is in the middle of a run; continue skips to the next number.
  • Line 6 (JS) / line 7 (Python): num is a start, so the run so far is 1 long.
  • Lines 7–8 (JS) / lines 8–9 (Python): keep asking about the next number up, num + length, and grow the run while the answer is yes.
  • Line 10 (both): keep the longest run seen.
  • Line 12 (JS) / line 11 (Python): return it.

One small difference: JavaScript visits a Set in the order values were added; Python visits a set in its own internal order. The order changes which start we meet first, but never the answer.

Dry run

numnum − 1 in set?start?countinglengthbest
10099: noyes101? no11
43: yesno, skip1
200199: noyes201? no11
10: noyes2? yes, 3? yes, 4? yes, 5? no44
32: yesno, skip4
21: yesno, skip4
nums = [100, 4, 200, 1, 3, 2] (JavaScript's visiting order)

The num = 1 row does all the real work: starting at 1, it walks the whole run 1–4. The rows for 4, 3 and 2 each cost a single lookup, because those numbers are already covered by that run.

Complexity

Brute force

Time

O(n³)

Up to n × n ÷ 2 searches (recounting runs from every number), each scanning up to n cells.

Space

O(1)

Only a few counters.

Sort, then walk

Time

O(n log n)

Sorting dominates; the walk afterwards is n steps.

Space

O(n)

The sorted copy.

Hash set, count only from starts

Time

O(n)

Each number gets one start check and is stepped on by at most one while loop, so at most about 3n lookups.

Space

O(n)

The set holds every distinct number.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “Sorting gives O(n log n). The problem wants O(n), so I’ll use a hash set for O(1) lookups.”
  2. “To avoid recounting, I only count from numbers whose predecessor is missing: the starts of runs.”
  3. “It’s O(n) even with the inner while: each number is visited at most once by any while loop.”
  4. Trace a small example, pointing out the skipped non-starts.

Likely follow-up questions:

  • “Return the sequence itself, not just its length?” Remember the start of the best run; the run is start, start + 1, …
  • “Why not a hash map?” We only need “is it here?”, not a value per key, so a set is enough.
  • “Could Union-Find solve this?” Yes, by joining each x with x + 1, but the set solution is simpler and just as fast.

Related problems:

  • Contains Duplicate (this week): the simplest use of a hash set’s instant lookup.
  • Two Sum (this week): asks the set-style question “is my partner here?” for a different partner (target − x instead of x + 1).
  • Top K Frequent Elements (this week): another problem where the follow-up asks you to beat O(n log n) without sorting.