LeetCode 128 · Arrays & Hashing

Longest Consecutive Sequence, explained with a picture

Beads on a ruler.

MediumArrays & Hashing
▶ Watch it step by step

The problem

Given an unsorted list of numbers, find the length of the longest run of consecutive numbers (like 1, 2, 3, 4). The run can be made from numbers anywhere in the list.

Input:  [9, 4, 1, 3, 2, 10, 15, 4]
Output: 4   (the run 1, 2, 3, 4)

Picture it

Imagine numbered beads spilled onto a ruler, each landing at its own number. A run is a row of beads with no gaps. We only start counting at a bead that has no bead just before it (it is the start of a run), then walk right while the next bead exists. That way every run is counted once.

How to recognise it

  • You need runs of consecutive values (x, x + 1, x + 2, ...), but the values can sit anywhere in the list.
  • The positions do not matter, only which values exist. That points to a set.
  • The problem asks for O(n) time, which rules out sorting (O(n log n)).
  • Up to 10^5 numbers between −10^9 and 10^9, so you cannot use the values as list indices.

Start with brute force

From every number x, count upwards for as long as the next value is in the list.

def longest_consecutive_brute(nums):
    best = 0
    for x in nums:
        length = 1
        while x + length in nums:      # list search: O(n) each time
            length += 1
        best = max(best, length)
    return best

Each in on a list scans it, so one run of length L costs O(L · n), and doing it from every start gives O(n³) in the worst case (one long run). With n = 10^5 that is hopeless: even a single scan from every start, 10^10 steps, is too slow. Space is O(1).

Sorting first and then counting runs of neighbours works in O(n log n), but the problem asks for O(n).

From brute force to the idea

  1. Make lookups fast. Put the numbers in a set, so x + 1 in s is O(1) on average. That alone gives O(n²) for one long run, because every number in the run counts the rest of it again.
  2. Find the waste. In the run 1, 2, 3, 4, counting from 2, 3 and 4 only repeats part of the count from 1.
  3. Only count from the start of a run. x starts a run exactly when x − 1 is not in the set. Every other number is in the middle of someone else's run, so skip it.
  4. Walk the run. From a start, step up while x + length is in the set, then compare with the best.
  5. Loop over the set, not the list. Duplicates then appear once, so no run start is counted twice.

This is the key idea: a set for O(1) lookups, and counting only from numbers with no left neighbour.

The key idea

Put everything in a set. Only start counting from numbers whose (x − 1) is missing. Each number is visited a constant number of times: O(n).

Python solution

def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:          # x starts a run
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n³) worst case: each step of each run scans the whole listO(1): a few counters
Set + run starts (shown code)O(n): the while loop only runs from run starts, so each number is stepped over onceO(n): the set

The inner while looks like it could make this O(n²). It cannot: the runs do not overlap, and their lengths add up to at most the number of distinct values.

Edge cases

  • Empty list: the set is empty, the loop never runs, and the answer is 0.
  • One number: returns 1.
  • Duplicates ([1, 2, 2, 3]): returns 3. The set removes the extra 2.
  • All equal ([5, 5, 5]): returns 1.
  • Negative numbers ([-2, -1, 0, 1]): returns 4; the check x - 1 not in s works across zero.
  • No two consecutive ([0, 2, 4]): every number starts a run of length 1, so the answer is 1.

Common mistakes

  • Starting a count from every number instead of only from run starts, which is O(n²) on one long run.
  • Looping for x in nums instead of for x in s. The answer stays right, but a run start repeated many times is counted again each time: n/2 copies of 1 followed by 2 to n/2 is O(n²).
  • Sorting and forgetting to skip equal neighbours, so [1, 2, 2, 3] looks like two runs of length 2.
Your turn: runs with a step

Find the longest run where each value is exactly d more than the previous one, using values from the list. For [1, 3, 5, 9, 7, 2] with d = 2 the answer is 5 (1, 3, 5, 7, 9). Describe your approach, then write it if you like.

Compare with our answer

Same set, same rule for where a run starts, with 1 replaced by d. x starts a run when x − d is missing, and the run continues while x + d · length is present.

def longest_step(nums, d):
    s = set(nums)
    best = 0
    for x in s:
        if x - d not in s:          # x starts a run
            length = 1
            while x + d * length in s:
                length += 1
            best = max(best, length)
    return best

With d = 1 it is the original problem. Each value still belongs to exactly one run, so time stays O(n) and space O(n).

A strong answer mentions: the start-of-run test with x − d, why each value is still visited once, and that d = 1 gives back the original.

Check what stuck

1. You are given the booked room numbers of a hotel, unsorted and possibly repeated, and must find the longest block of neighbouring rooms that are all booked, in O(n). Which approach fits best?

2. Why is the shown code O(n) even though it has a while loop inside a for loop?

3. A learner writes for x in nums: instead of for x in s:. Which input now makes the code noticeably slow?

Score 60% or more and the lesson is marked complete.