💬 Discord
Sign In
NeetCode #105LC-128MediumArrays & HashingBlind 75NC 150NC 250
← Back to All Problems

#105 · #128 · Longest Consecutive Sequence(最长连续序列)

📌 Problem Statement & Constraints

Given an unsorted array of integers nums, return the length of the longest run of consecutive integers. The elements need not be adjacent in the array. Constraints: 0 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9. The algorithm must run in O(n).

💡 Core Algorithmic Approaches

  1. Sorting would give O(n log n), which the O(n) requirement forbids. A hash set gives O(1) membership tests.
  2. Put every element into a set. Then for each element, ask: is x - 1 also in the set?
  3. If yes, x is not the start of a run, so skip it. This is the crucial trick -- it guarantees each element is expanded at most once overall.
  4. If no, x starts a run. Walk upward with x + 1, x + 2, ... while the set contains them, and record the run length.

💻 Benchmark Python3 Implementation

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        best = 0
        for x in s:
            if x - 1 in s:          # not the start of a run -> skip
                continue
            length = 1
            while x + length in s:  # extend the run upward
                length += 1
            best = max(best, length)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) amortised. Although there is a nested while, the inner loop only runs for elements that start a run, and each element belongs to exactly one run -- so total inner iterations across the whole algorithm are at most n.
💾 Space Complexity
O(n) for the set. Note the input array is not modified, and duplicate values collapse in the set, which is exactly what we want.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the x - 1 in s guard: every element would then expand its full run, giving O(n^2) on inputs like [1, 2, 3, ..., n].
  • Sorting and scanning: correct and simple, but O(n log n) violates the stated O(n) requirement.
  • Iterating over nums instead of s: works, but duplicates cause redundant work; iterating the set is cleaner.
  • Handling the empty array: set() is empty, the loop body never runs, and best stays 0 -- which is the expected answer, so no special case is needed.