Longest Consecutive Sequence

Sorting would make consecutive runs trivial to spot, but that costs O(n log n) and the problem demands linear time. The trick to get there without sorting: put every number in a hash set, then only ever start counting a run from a number that is the start of one — a number whose predecessor (num - 1) is not in the set. Every element gets examined by at most two constant-time set lookups over the whole algorithm, never revisiting the middle of a run twice.

Sort First

Time O(n log n)Space O(n)

Sort the (deduplicated) numbers, then scan once counting how long each run of consecutive values lasts.

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if not nums:
            return 0
        nums = sorted(set(nums))
        longest = 1
        current = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1] + 1:
                current += 1
                longest = max(longest, current)
            else:
                current = 1
        return longest

Correct and only O(n) after sorting, but the sort itself is O(n log n) — more than the follow-up allows.

Hash Set, Start-of-Sequence Only

OptimalTime O(n)Space O(n)

Put every number in a set. For each number, only start extending a sequence if it is a sequence start — meaning num - 1 is not in the set. From a true start, walk forward (num + 1, num + 2, …) counting how far the run goes. Numbers in the middle of a run are skipped as starting points entirely, so each element is only ever walked over once across the whole algorithm.

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        num_set = set(nums)
        longest = 0
        for num in num_set:
            if num - 1 not in num_set:
                length = 1
                while num + length in num_set:
                    length += 1
                longest = max(longest, length)
        return longest

Watch the single probe that decides everything: when num - 1 is absent a new run starts, and when it is present the number is skipped as a middle element.

Input array

100

200

Hash set

100

200

Set lookup

num—probe—

Lookup: —

Run from —

no run yet

length = 0longest = 0

1 / 14

current candidateprobing the setrun being builtalready handled

Build the hash set from all six numbers. Rule: only expand a run from a number whose predecessor num - 1 is absent, so no run is ever counted twice.

Numbers 4, 3, and 2 are never used as starting points at all — each has num - 1 in the set, so the if skips them, which is exactly what keeps the total work linear.

Correctness: every consecutive run has exactly one true start (the number with no predecessor in the set), so every run gets expanded from that start exactly once — no run is ever counted twice, and no run is ever missed, since every number that is a start is checked.

Complexity: building the set is O(n). Across the whole loop, the inner while only advances through numbers that belong to a run being expanded from its true start, so every number is visited by the inner loop at most once in total — O(n) time overall, not O(n²). The set holds up to n numbers — O(n) space.

Longest Consecutive Sequence

Sort First

Hash Set, Start-of-Sequence Only

More Arrays & Hashing practice