Longest Consecutive Sequence (LeetCode 128)

The problem

You get an unsorted array of integers nums. Return the length of the longest sequence of consecutive integers you can form from its values (like 4, 5, 6, 7). The values can be in any order in the array. Your algorithm must run in O(n) time.

Input:  [100, 4, 200, 1, 3, 2]
Output: 4

The values 1, 2, 3 and 4 form a run of four. 100 and 200 are runs of length one.

How to think about it

Start with brute force. Sort the array and scan it, extending the current run when the next value is one more and resetting otherwise. That’s O(n log n), simple and correct, but the problem demands O(n), so sorting is off the table.

First idea: a set gives O(1) “is x + 1 here?“. Put every value in a set. Then for each x, walk upwards x + 1, x + 2, … while the values exist. That finds every run, but it’s O(n²) in the worst case: on 1, 2, …, n, you walk the long run from every one of its members.

The key insight: only start counting at the beginning of a run. A value x is the start of a run exactly when x − 1 is not in the set. If x − 1 is there, x is in the middle of someone else’s run, so skip it; that run will be counted from its own start. Now every run is walked once, from its start, and the total number of upward steps across all runs is at most n.

Which pattern is this? Hash set lookups. The tell is “O(n) on unsorted data, where sorting would make it easy”.

Approach

1. Put all values in a set s. This also removes duplicates.
2. For each x in the set:
   • if x − 1 is in the set, skip it: it’s not a run start;
   • otherwise walk y up from x while y + 1 is in the set.
3. The run length is y − x + 1; keep the maximum in best.
4. Return best.

Solution

def longest_consecutive(nums):
    s = set(nums); best = 0
    for x in s:
        if x - 1 not in s:                  # x starts a run
            y = x
            while y + 1 in s: y += 1        # walk to the end of the run
            best = max(best, y - x + 1)
    return best
# longest_consecutive([100,4,200,1,3,2]) -> 4

Looping over the set rather than nums matters: with many duplicates of a run start, looping over nums would walk the same run repeatedly.

Dry run

On [100, 4, 200, 1, 3, 2]. The set’s iteration order below is what CPython produced; any order gives the same answer.

It returns 4. On [0, 3, 7, 2, 5, 8, 4, 6, 0, 1] it returns 9 (the run 0 to 8).

Complexity

• Time: O(n). Building the set is O(n). Each value is checked once as a possible start, and each value is stepped over at most once by the upward walk from its run’s start.
• Space: O(n) for the set.

Edge cases and pitfalls

• Empty array: the loop never runs, and it returns 0.
• Duplicates: [1, 2, 0, 1] returns 3. The set removes the extra 1.
• Negative numbers work the same way: x − 1 is just another integer.
• Skipping the start check keeps the code correct but makes it O(n²) on long runs, which can time out.
• Union-find also solves this in near-O(n), but the set solution is shorter and easier to defend.

Related problems

• Contains Duplicate (LeetCode 217): a set as the whole solution.
• Two Sum (LeetCode 1): O(1) membership checks for a related value.
• Number of Connected Components (LeetCode 323): the union-find way of thinking about “which values belong together”.