Week 1 · Arrays & Hashing

Longest Consecutive Sequence

Find the length of the longest run of consecutive integer values, regardless of input order.

Medium Arrays & Hashing Week 1 Practice runner

Frame the problem

The sequence is by value, not by index adjacency.
Duplicates should not inflate the length.
The target interview solution is O(n).

1. Reveal example inputs and outputs

Example 1

Input:

longest_consecutive([
  100,
  4,
  200,
  1,
  3,
  2
])

Output:

Example 2

Input:

longest_consecutive([
  0,
  3,
  7,
  2,
  5,
  8,
  4,
  6,
  0,
  1
])

Output:

2. Brute force first

If you started from every number and walked upward, which starts repeat work already done by earlier sequence members?

3. Reveal the insight ladder

Put all values in a set.
Only start a scan at value x if x - 1 is absent.
Walk upward while x + length exists.
Each sequence is counted once from its true start.

4. Dry run before code

nums = [100, 4, 200, 1, 3, 2].
Only 1, 100, and 200 have no predecessor.
Starting at 1 walks 1, 2, 3, 4 for length 4.

5. Reveal final Python solution

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for value in values:
        if value - 1 in values:
            continue
        length = 1
        while value + length in values:
            length += 1
        best = max(best, length)
    return best

Complexity: Time O(n) average, space O(n).

Interview narration

The important invariant is that I only expand from sequence starts.
That prevents revisiting the same consecutive run from every interior value.
The set gives O(1) average membership checks.

Common traps

Sorting and missing the O(n) target.
Counting from every value, which can degrade to O(n^2).
Letting duplicates inflate the length.

Follow-up drills

1. Why does the while loop not make this O(n^2)?

Because it only runs from starts. Across all starts, each consecutive value participates in one expansion of its sequence.

2. What if you also need the sequence itself?

Track the best start and length, then return range(best_start, best_start + best_length) or the equivalent list.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.