Longest Consecutive Sequence

PracticeNeetCode ↗LeetCode ↗

Given an unsorted array of integers nums, return the length of the longest run of consecutive integers it contains — in O(n) time (no sorting).

Example

Key Pointers

• Sorting solves this in O(n log n); the set-based trick is what gets it down to O(n).
• The key insight: only start counting from a number that is the start of a run — i.e. num - 1 is not in the set.
• Because each number only ever gets "extended from" once (as part of its run's single start), the total work across all starts stays linear.

Step-by-Step Analysis

1. Put every number into a hash set for O(1) lookups.
2. For each number n in the set, check if n - 1 is also in the set — if it is, skip (n isn't a run's start).
3. If n is a start, count forward: while n + length is in the set, increment length.
4. Track the maximum length seen across all starts, and return it.

Complexity

Time: O(n) — Space: O(n)

Code

def longestConsecutive(nums: list[int]) -> int:
    num_set = set(nums)
    longest = 0

    for n in num_set:
        if n - 1 not in num_set:
            length = 1
            while n + length in num_set:
                length += 1
            longest = max(longest, length)

    return longest

Code Explanation

How the solution above works, piece by piece.

1. num_set = set(nums): O(1) membership checks, and duplicates disappear.
2. if n - 1 not in num_set: only begin counting at the start of a run. For 2, 3, 4 this is false, so they are skipped.
3. while n + length in num_set: length += 1: walk right from the start as long as the next number exists.
4. longest = max(longest, length) keeps the best run.
5. Every number is visited by the while loop at most once (only from its own run's start), so O(n) total instead of O(n log n) for sorting.

Visual Walkthrough

Running it on nums = [100, 4, 200, 1, 3, 2]:

Video Explanation

NeetCode — Hashmaps & Sets, LeetCode 128