Exploring the Longest Consecutive Sequence in Data Structures

Problem Statement

You’re given an unsorted list of integers. You need to find the length of the longest sequence of numbers that appears consecutively (without gaps), in any order.

Real-life Analogy:
Imagine you have random shirt numbers from a football team: [100, 4, 200, 1, 3, 2].
The longest streak of consecutive numbers is 1, 2, 3, 4 → Answer: 4.

Why This Problem is Important

• Real-world:

  • Timeline analysis (continuous days of activity).

  • Version control (sequential updates).

Interviews:

• Tests hash-set operations and algorithm optimization.

• Classic example of improving brute-force (O(n log n)) to optimal (O(n)).

Optimal Algorithm: HashSet + Smart Traversal

Why HashSet?

• O(1) lookups to check if a number exists.

• Avoids sorting (O(n log n)) → achieves O(n) time.

Step-by-Step Approach

Brute Force (O(n log n))

1. Sort the array.

2. Traverse to find consecutive sequences.

Optimized (O(n) Time, O(n) Space)

1. Convert the list to a set (for O(1) lookups).

2. For each number in the set:

   • Check if it’s a sequence start: If num - 1 is not in the set.

   • Count the sequence: Increment while num + 1 exists.

   • Track the longest streak.

Python Code (Corrected)

from typing import List

class Solution:  # Fixed typo in "Solution"
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)      # Step 1: O(n) space
        longest = 0               # Track max streak

        for num in num_set:       # Step 2: O(n) time
            if num - 1 not in num_set:  # Start of a sequence
                current = num
                length = 1

                while current + 1 in num_set:  # Step 3: Count sequence
                    current += 1
                    length += 1  # Fixed "++" to "+="

                longest = max(longest, length)  # Step 4: Update max

        return longest

Code Explanation

Dry Run Example

Input: [100, 4, 200, 1, 3, 2]
Set: {1, 2, 3, 4, 100, 200}

1. 100:

   • 99 not in set → sequence starts.

   • 101 not in set → streak = 1.

2. 4:

   • 3 exists → skip (not a start).

3. 1:

   • 0 not in set → sequence starts.

   • 2, 3, 4 exist → streak = 4.
     Result: 4.

Complexity Analysis

• Time: O(n) (each number processed once).

• Space: O(n) (for the set).

Key Takeaways

1. HashSet is optimal for O(1) lookups.

2. Check num - 1 to avoid redundant work.

3. Interviews: Expect this in FAANG coding rounds.