Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is an unsorted integer array. The task is to find the length of the longest run of values that can be arranged as x, x + 1, x + 2, ....

The original order of the array does not matter. Duplicates also do not make a run longer. The only thing that matters is whether neighboring integer values exist somewhere in the input.

The real challenge is the constraint that the solution must run in O(n) time. That requirement rules out the most obvious approach.

The natural baseline

If the time limit were ignored, sorting would be the simplest way to think about the problem:

  • sort the array
  • walk from left to right
  • grow the current streak when the next number is exactly +1
  • ignore duplicates

That approach is easy to reason about, and it is a useful first draft. But it costs O(n log n) because of the sort, so it is not the optimal answer.

The key insight

The expensive question is: for a given number, does the next number exist?

A hash set answers that in O(1) average time.

Once all numbers are in a set, there is only one subtle optimization needed: start counting a streak only from numbers that do not have a predecessor.

In other words, only start from value when value - 1 is not in the set.

That rule avoids repeated work:

  • if 4 has 3 in the set, then 4 is in the middle of a streak
  • scanning forward from 4 would duplicate work already done when the streak started earlier
  • only true starting points should launch a forward scan

How to derive the optimal solution

A practical way to derive the final algorithm is:

  1. Notice that sorting makes the logic simple but misses the required time bound.
  2. Replace sorting with a hash set so membership checks become fast.
  3. Realize that every streak has exactly one valid starting point: the first number whose predecessor is missing.
  4. From each such start, walk forward until the streak ends and track the longest length seen.

Duplicates stop being a problem automatically because the set stores each number only once.

Best approach

The hash-set start-of-sequence approach is the right default:

  • Time: O(n) on average
  • Extra space: O(n)
  • Why it works: each distinct value is inserted once, and forward scans only begin at real sequence starts

Python solution

from typing import Iterable, List, Set


def build_unique_number_set(numbers: Iterable[int]) -> Set[int]:
    """Return the distinct numbers for fast membership checks."""
    return set(numbers)


def measure_streak_from_start(start_value: int, unique_numbers: Set[int]) -> int:
    """Count the consecutive run length that begins at start_value."""
    current_value = start_value
    streak_length = 1

    while current_value + 1 in unique_numbers:
        current_value += 1
        streak_length += 1

    return streak_length


def longest_consecutive_run_length(numbers: List[int]) -> int:
    """Return the length of the longest consecutive run in the input."""
    unique_numbers = build_unique_number_set(numbers)
    longest_streak_length = 0

    for value in unique_numbers:
        # Only scan forward from the first value in a streak.
        if value - 1 in unique_numbers:
            continue

        streak_length = measure_streak_from_start(
            start_value=value,
            unique_numbers=unique_numbers,
        )
        longest_streak_length = max(longest_streak_length, streak_length)

    return longest_streak_length


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        return longest_consecutive_run_length(nums)

Why this works

The set gives instant access to the question “does the next integer exist?” That makes it possible to grow streaks without sorting.

The predecessor check is what keeps the runtime linear. If a number has a smaller neighbor, it is in the middle of a streak, so the algorithm skips it. That means each streak is measured exactly once from its left edge instead of being restarted from every number inside it.

The interview version to remember is:

put every number in a set, start only at numbers with no predecessor, then count forward until the streak breaks.