Longest Consecutive Sequence

128. Longest Consecutive Sequence

Medium

Return the length of the longest consecutive elements sequence in O(n) time.

ArrayHash TableUnion Find

View Problem

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.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements 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

Example 3:

Input: nums = [1,0,1,2]
Output: 3

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

Try It Yourself

TypeScript

function longestConsecutive(nums: number[]): number {
    // Your solution here
}

Go

func longestConsecutive(nums []int) int {
    // Your solution here
}

Solution

Click to reveal solution

Use a hash map with memoization to find consecutive sequences efficiently.

TypeScript Solution

function longestConsecutive(nums: number[]): number {
  if (!nums.length) {
      return 0;
  }
  
  const store: Record<number, number> = {};

  for (const num of nums) {
      store[num] = -1;
  }

  Object.keys(store).forEach(key => searchSequence(+key, store));

  return Math.max(...Object.values(store));
}

function searchSequence(num: number, store: Record<number, number>): number {
  if (!(num in store)) {
      return 0;
  }

  if (store[num] === -1) {
      const prev = searchSequence(num - 1, store);
      store[num] = prev + 1;
  }

  return store[num];
}

Time:O(n)

Space:O(n)

Go Solution

func longestConsecutive(nums []int) int {
  if len(nums) == 0 {
      return 0
  }
  
  store := make(map[int]int)
  
  // Initialize all numbers with -1
  for _, num := range nums {
      store[num] = -1
  }
  
  // Search sequence for each number
  for num := range store {
      searchSequence(num, store)
  }
  
  // Find maximum length
  maxLen := 0
  for _, length := range store {
      if length > maxLen {
          maxLen = length
      }
  }
  
  return maxLen
}

func searchSequence(num int, store map[int]int) int {
  if _, exists := store[num]; !exists {
      return 0
  }
  
  if store[num] == -1 {
      prev := searchSequence(num-1, store)
      store[num] = prev + 1
  }
  
  return store[num]
}

Time:O(n)

Space:O(n)

Algorithm (Memoized Approach):

1. Store all numbers in a hash map with initial value -1
2. For each number, recursively search for its predecessor
3. Use memoization to cache sequence lengths
4. Return the maximum sequence length found

Time Complexity: O(n) - Each number is processed at most twice Space Complexity: O(n) - Hash map storage

Alternative Set-Based Approach:

function longestConsecutive(nums: number[]): number {
    if (nums.length === 0) return 0;
    
    const numSet = new Set(nums);
    let maxLength = 0;
    
    for (const num of numSet) {
        // Only start counting if this is the beginning of a sequence
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let currentLength = 1;
            
            // Count consecutive numbers
            while (numSet.has(currentNum + 1)) {
                currentNum++;
                currentLength++;
            }
            
            maxLength = Math.max(maxLength, currentLength);
        }
    }
    
    return maxLength;
}

Key Insight: Only start counting from numbers that don't have a predecessor (num - 1), ensuring each sequence is counted only once for optimal O(n) performance.