Longest Consecutive Sequence

May 2025

Subsets is the canonical introduction to the concept of backtracking.

While this problem can be solved without backtracking via iteration, the backtracking solution introduces the basic algorithm structure that will be expanded on in future, more complicated problems like Subsets II and Permutations.

Longest Consecutive Sequence
Solved
Medium
Topics
Companies
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 <= 105
-109 <= nums[i] <= 109

Solution

The backtracking-based function uses backtracking to progressively explore the solution set. The key insight is the creation and maintenance of the current subset, which is added to, and then removed from, as the traversal takes place across the solution space.

func longestConsecutive(nums []int) int {    
    set := make(map[int]struct{}) // set to store our numbers
    max := 0

    // load nums into the nums set
    for _, num := range nums {
        set[num] = struct{}{}
    }

    // loop through nums and see if each is a poss. seq. start
    for _, num := range nums {
        if _, ok := set[num - 1]; !ok {
            length := 1
            delete(set, num)
            // this is a seq start because num - 1 missing
            for {
                if _, ok := set[num + length]; ok {
                    delete(set, num + length)
                    length++
                } else {
                    break
                }
            }

            if length > max {
                max = length
            }
        }
    }

    return max
}

Breakdown:

  1. seenIndices Map: This hash map stores numbers encountered (key) and their original indices (value). This is the cornerstone of the $O(n)$ solution.
  2. Single Iteration: The nums array is traversed once.
    • For each currentNum, the complement needed to reach target is calculated.
    • seenIndices.has(complement): This $O(1)$ average-time lookup checks if the complement was previously stored.
      • If true: The pair is found. The stored index of the complement and the current index i are returned.
      • If false: currentNum (and its index i) is added to seenIndices, making it available as a potential complement for future elements.
  3. Error Handling: The throw new Error addresses scenarios where input constraints (guaranteed solution) might not hold, crucial for robust API design beyond typical LeetCode settings.

Performance:

  • Time Complexity: $O(n)$. A single pass with constant-time average map operations. This is optimal as each element must be visited at least once.
  • Space Complexity: $O(n)$. In the worst case, the seenIndices map may store up to $n-1$ elements. This space usage is a direct trade-off for achieving $O(n)$ time.

Suboptimal Alternatives:

  1. Brute Force ($O(n^2)$ time, $O(1)$ space): Nested loops checking every pair. Unacceptably slow for non-trivial inputs due to its quadratic time complexity.

  2. Sorting + Two Pointers ($O(n \log n)$ time, $O(1)$ or $O(n)$ space): Sorting the array first ($O(n \log n)$), then using a two-pointer scan ($O(n)$).

    • Time Inefficiency: Immediately slower than the $O(n)$ hash map approach.
    • Index Management: Sorting disrupts original indices. Tracking them requires auxiliary data structures (adding $O(n)$ space) or complex mapping, negating simplicity and often the $O(1)$ space benefit for this specific problem variant. For the standard Two Sum requiring original indices, this method introduces unnecessary complexity and performance degradation compared to the hash map solution.

Conclusion:

The single-pass hash map approach to Two Sum is not merely a solution; it is the direct, efficient, and standard solution for the given constraints. It demonstrates a clear understanding of data structure strengths and time-space trade-offs. Anything less efficient for this problem typically indicates a misapplication of patterns or a misunderstanding of these core engineering principles.

May 2025