Problem Description

You are given an unsorted array of integers called nums. Your task is to find the length of the longest sequence of consecutive integers that can be formed using the elements from the array.

For example, if you have the array [100, 4, 200, 1, 3, 2], the longest consecutive sequence would be [1, 2, 3, 4], which has a length of 4.

Key requirements:

• The elements don't need to be consecutive in the original array - they just need to exist in the array
• You need to find consecutive integers (like 1, 2, 3, 4...)
• Return the length of the longest such sequence
• Your algorithm must run in O(n) time complexity, where n is the number of elements in the array

The challenge is to achieve this linear time complexity, which means you cannot sort the array first (as sorting would take O(n log n) time).

Intuition

To achieve O(n) time complexity, we need to avoid sorting. The key insight is to use a hash set for O(1) lookups to check if a number exists in our array.

The main idea is to build consecutive sequences incrementally. For each number x in the array, we can ask: "What's the longest consecutive sequence that starts from x?" To find this, we keep checking if x+1, x+2, x+3, and so on exist in our set until we find a number that doesn't exist.

However, there's a subtle optimization here. If we've already processed a number as part of a sequence, we don't need to process it again. So when we find consecutive numbers starting from x, we remove them from our set to avoid redundant work.

The clever part of this solution is using dynamic programming with memoization. We use a hash table d to store the length of the consecutive sequence for each processed endpoint. When we process a number x and find its sequence extends to y-1 (meaning y is the first number not in the sequence), we can say:

• The length of the sequence starting at x is (y - x) plus any sequence that might continue from y
• This is captured as d[x] = d[y] + y - x

This way, if we later encounter a number that connects to a previously processed sequence, we can reuse the already computed length instead of recalculating it.

By processing each number at most once (removing it from the set when processed) and using hash operations that are O(1), we maintain the overall O(n) time complexity.

Solution Approach

We implement the solution using hash tables to achieve O(n) time complexity. Here's the step-by-step approach:

1. Initialize Data Structures:

   • Create a hash set s containing all elements from nums for O(1) lookup
   • Initialize ans = 0 to track the maximum sequence length found
   • Create a hash table d using defaultdict(int) to store the length of consecutive sequences

2. Process Each Element: For each element x in the array:

   a. Find the Sequence Endpoint:

   • Start with y = x
   • While y exists in set s:
     • Remove y from s (to avoid reprocessing)
     • Increment y by 1
   • After the loop, y is the first number not in the sequence starting from x

   b. Calculate Sequence Length:

   • The sequence from x extends to y-1
   • The length is calculated as: d[x] = d[y] + y - x
     • y - x gives the length of the current sequence
     • d[y] adds any previously computed sequence starting from y

   c. Update Maximum:

   • Update ans = max(ans, d[x])

3. Return Result: Return ans as the length of the longest consecutive sequence

Key Insights:

• By removing elements from set s as we process them, each element is examined exactly once, ensuring O(n) time complexity
• The hash table d enables us to chain sequences together efficiently. If we previously found a sequence starting at position y, we can reuse that result
• The defaultdict(int) ensures d[y] returns 0 if y hasn't been processed yet, which correctly handles standalone sequences

Example Walkthrough: For nums = [100, 4, 200, 1, 3, 2]:

• Processing 100: finds sequence [100], length = 1
• Processing 4: finds sequence [4], length = 1 (1,2,3 not processed yet)
• Processing 200: finds sequence [200], length = 1
• Processing 1: finds sequence [1,2,3,4], removes all four from set, d[1] = d[5] + 5 - 1 = 0 + 4 = 4
• Processing 3 and 2: already removed from set, skipped in while loop
• Result: ans = 4

Example Walkthrough

Let's walk through the solution with nums = [100, 4, 200, 1, 3, 2]:

Initial Setup:

• Set s = {100, 4, 200, 1, 3, 2}
• Hash table d = {} (empty)
• Maximum length ans = 0

Processing each element:

Step 1: Process x = 100

• Start with y = 100
• Check if 100 is in set? Yes → Remove 100 from set, increment y to 101
• Check if 101 is in set? No → Stop
• Calculate: d[100] = d[101] + (101 - 100) = 0 + 1 = 1
• Update: ans = max(0, 1) = 1
• Set now: s = {4, 200, 1, 3, 2}

Step 2: Process x = 4

• Start with y = 4
• Check if 4 is in set? Yes → Remove 4 from set, increment y to 5
• Check if 5 is in set? No → Stop
• Calculate: d[4] = d[5] + (5 - 4) = 0 + 1 = 1
• Update: ans = max(1, 1) = 1
• Set now: s = {200, 1, 3, 2}

Step 3: Process x = 200

• Start with y = 200
• Check if 200 is in set? Yes → Remove 200 from set, increment y to 201
• Check if 201 is in set? No → Stop
• Calculate: d[200] = d[201] + (201 - 200) = 0 + 1 = 1
• Update: ans = max(1, 1) = 1
• Set now: s = {1, 3, 2}

Step 4: Process x = 1

• Start with y = 1
• Check if 1 is in set? Yes → Remove 1 from set, increment y to 2
• Check if 2 is in set? Yes → Remove 2 from set, increment y to 3
• Check if 3 is in set? Yes → Remove 3 from set, increment y to 4
• Check if 4 is in set? No (already removed) → Stop
• Calculate: d[1] = d[4] + (4 - 1) = 1 + 3 = 4
  • Note: d[4] = 1 from Step 2, representing the sequence [4]
  • We're connecting sequences [1,2,3] + [4] = [1,2,3,4]
• Update: ans = max(1, 4) = 4
• Set now: s = {} (empty)

Step 5: Process x = 3

• Start with y = 3
• Check if 3 is in set? No (already removed in Step 4) → Stop immediately
• No updates needed

Step 6: Process x = 2

• Start with y = 2
• Check if 2 is in set? No (already removed in Step 4) → Stop immediately
• No updates needed

Final Result: ans = 4

The longest consecutive sequence is [1, 2, 3, 4] with length 4. The algorithm efficiently found this by processing each number once and connecting the sequences through the hash table d.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums.

Although there is a nested while loop structure, each element is processed at most twice - once when it's encountered in the outer loop and once when it's removed from the set in the inner while loop. Since each element can only be removed from the set once, the total number of operations across all iterations is bounded by 2n, which simplifies to O(n).

The space complexity is O(n), where n is the length of the array nums.

This is because:

• The set s stores at most n unique elements from the input array
• The dictionary d can store at most n key-value pairs (one for each unique starting point of a consecutive sequence)
• Both data structures together require O(n) space

Common Pitfalls

Pitfall 1: Not Handling the Starting Point Correctly

The Problem: A common mistake is trying to find sequences by only looking forward from each number, without considering whether the current number is actually the start of a sequence. This can lead to redundant work and incorrect sequence building.

Incorrect Approach:

# WRONG: Processing every number as a potential sequence member
for num in nums:
    count = 1
    current = num
    while current + 1 in num_set:
        current += 1
        count += 1
    max_length = max(max_length, count)

This approach has a critical flaw: it processes subsequences multiple times. For example, with [1, 2, 3, 4], it would check sequences starting from 2, 3, and 4, not just from 1.

The Solution: Only start building a sequence if the current number is actually the beginning of a sequence (i.e., num - 1 is not in the set):

for num in nums:
    # Only start a sequence if this is the beginning
    if num - 1 not in num_set:
        current = num
        count = 1
        while current + 1 in num_set:
            current += 1
            count += 1
        max_length = max(max_length, count)

Pitfall 2: Modifying the Set While Iterating Over It

The Problem: Attempting to iterate over the set while simultaneously removing elements from it:

# WRONG: This will raise RuntimeError
for num in remaining_numbers:  # Iterating over the set
    while num in remaining_numbers:
        remaining_numbers.remove(num)  # Modifying during iteration
        num += 1

The Solution: Iterate over the original array instead of the set, then check membership and remove from the set:

# CORRECT: Iterate over the original array
for num in nums:
    if num not in remaining_numbers:
        continue
    # Now safe to modify remaining_numbers
    while num in remaining_numbers:
        remaining_numbers.remove(num)
        num += 1

Pitfall 3: Overcomplicated Sequence Chaining Logic

The Problem: The dictionary caching mechanism (sequence_lengths) in the provided solution adds unnecessary complexity. The line:

current_length = (sequence_end - current_num) + sequence_lengths.get(sequence_end, 0)

This attempts to chain sequences, but since we're removing elements from the set as we process them, sequence_lengths.get(sequence_end, 0) will almost always return 0, making the dictionary redundant.

The Solution: Simplify by removing the unnecessary dictionary:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
          
        num_set = set(nums)
        max_length = 0
      
        for num in num_set:
            # Only start counting if this is the beginning 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
              
                max_length = max(max_length, current_length)
      
        return max_length

This cleaner approach maintains O(n) complexity while being more readable and less error-prone.