Skip to main content

🟨 Longest Consecutive Sequence (#128)

🔗 Problem Link​

📋 Problem Statement​

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

💡 Examples​

Example 1​

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2​

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

🔑 Key Insights & Approach​

Core Observation: Only start counting from numbers that are the beginning of a sequence (no num-1 exists).

Why HashSet?

  • O(1) lookup to check if number exists
  • Avoid sorting which would be O(n log n)
  • Only start sequences from "start" numbers

Approaches:

  1. Sort and scan: O(n log n)
  2. HashSet with intelligent start detection: O(n) - optimal

Pattern: "Sequence Building" pattern using set for O(1) lookups.

🐍 Solution: Python​

Approach: HashSet with Smart Start Detection​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import List

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

        num_set = set(nums)
        longest = 0

        for num in num_set:
            # Only start counting if this is the start of a sequence
            if num - 1 not in num_set:
                current_num = num
                current_length = 1

                # Count consecutive numbers
                while current_num + 1 in num_set:
                    current_num += 1
                    current_length += 1

                longest = max(longest, current_length)

        return longest

Approach 2: With Union-Find (Alternative)​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import List

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

        num_set = set(nums)
        longest = 0

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

        return longest

🔵 Solution: Golang​

Approach: HashSet with Smart Start Detection​

Time Complexity: O(n) | Space Complexity: O(n)

func longestConsecutive(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    // Create set
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }

    longest := 0

    for num := range numSet {
        // Only start if this is the beginning of a sequence
        if !numSet[num-1] {
            currentNum := num
            currentLength := 1

            // Count consecutive numbers
            for numSet[currentNum+1] {
                currentNum++
                currentLength++
            }

            if currentLength > longest {
                longest = currentLength
            }
        }
    }

    return longest
}

📚 References​