NEETCODE - Arrays and Hashing: Longest Consecutive Sequence

Set-Based Sequence Detection: From O(n log n) Sorting to O(n) Hash Lookups

Technology: Python, Algorithms
Skill: Hash Sets, Sequence Detection

Problem Statement

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

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

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

Example 1:
Input: nums = [2,20,4,10,3,4,5]
Output: 4
Explanation: The longest consecutive sequence is [2, 3, 4, 5].

Example 2:
Input: nums = [0,3,2,5,4,6,1,1]
Output: 7
Explanation: The longest consecutive sequence is [0, 1, 2, 3, 4, 5, 6].

Constraints:

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

Solutions Progression

Approach 1: Sort and Scan (Intuitive but Violates Constraint)

The most intuitive approach: sort the array and find the longest consecutive run.

from typing import List

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

# Sort and remove duplicates
        sorted_nums = sorted(set(nums))

max_length = 1
        current_length = 1

for i in range(1, len(sorted_nums)):
            if sorted_nums[i] == sorted_nums[i-1] + 1:
                current_length += 1
                max_length = max(max_length, current_length)
            else:
                current_length = 1

return max_length

Time Complexity: O(n log n)

• Sorting: O(n log n) - dominant operation
• Single scan: O(n)
• Total: O(n log n)

Space Complexity: O(n)

• Sorted array: O(n)
• Converting to set removes duplicates: O(n)

Approach 2: Sort Without Set Conversion (Handles Duplicates)

A variation that handles duplicates more carefully during the scan.

from typing import List

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

sorted_nums = sorted(nums)

max_length = 1
        current_length = 1

for i in range(1, len(nums)):
            if sorted_nums[i] == sorted_nums[i-1] + 1:
                current_length += 1
                max_length = max(max_length, current_length)
            elif sorted_nums[i] == sorted_nums[i-1]:
                continue
            else:
                current_length = 1

return max_length

Time Complexity: O(n log n)
Space Complexity: O(n) for sorted array (or O(1) if sorting in-place)

Approach 3: Hash Set with Sequence Start Detection (Optimal)

Use a hash set for O(1) lookups and only start counting from sequence beginnings.

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_length = 0

for num in num_set:
            if num - 1 not in num_set:
                current_length = 0
                while num + current_length in num_set:
                    current_length += 1
                max_length = max(max_length, current_length)

return max_length

Time Complexity: O(n)

Space Complexity: O(n)

Approach 4: Hash Set with Bidirectional Search (Alternative)

An alternative that builds sequences by looking both directions from each unvisited number.

from typing import List

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        visited = set()
        max_length = 0

for num in num_set:
            if num in visited:
                continue

left = num - 1
            while left in num_set:
                visited.add(left)
                left -= 1

right = num + 1
            while right in num_set:
                visited.add(right)
                right += 1

length = right - left - 1
            max_length = max(max_length, length)
            visited.add(num)

return max_length

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

Pattern Recognition

Core Pattern: Hash Set for O(1) Membership + Sequence Start Detection

Bridge to Real Systems

Where This Algorithm Lives in Production

1. Database Gap Detection
2. Log Analysis
3. Time Series Data Analysis
4. Network Packet Reassembly
5. Version Control Systems

Mini-System Evolution

1. Basic Consecutive Sequence
2. Report Actual Sequences
3. Stream Processing
4. Distributed Processing

Key Takeaways

1. Hash sets enable O(1) membership checks.
2. Sequence start detection is the key insight.
3. Nested loops can still be O(n).
4. Sorting is not always necessary.
5. Space-time trade-off.
6. This pattern appears in many domains.