Hashing for Longest Consecutive Subsequence

1. Understanding the Problem

First, let's clearly define the problem. You are given an unsorted array of integers, and you need to find the length of the longest sequence of consecutive numbers. The numbers in the sequence do not need to be contiguous in the input array.

For example, given nums = [100, 4, 200, 1, 3, 2], the longest consecutive sequence is [1, 2, 3, 4]. Its length is 4.

The following video provides a great introduction to the problem and walks through a couple of initial, less-than-optimal ideas.

As you saw, the brute-force method is too slow. A better, but still not optimal, solution would be to sort the array first. Sorting takes $O(n\log n)$ time. After sorting, you could find the longest consecutive sequence in a single pass ($O(n)$). The total time complexity would be dominated by sorting, resulting in $O(n\log n)$.

Our goal, driven by interview and competitive programming standards, is to achieve a linear, $O(n)$ time solution. This is where hashing comes in.

2. The Optimal Solution with Hashing

The key to an $O(n)$ solution is to perform fast lookups to check if a number's neighbors exist. A HashSet is the perfect data structure for this, providing $O(1)$ average time for contains() checks.

The high-level plan is:

1. Insert all elements of the array into a HashSet to get rid of duplicates and enable fast lookups.
2. Iterate through the numbers and, for each number, try to build the longest possible sequence around it.

However, a naive implementation of step 2 would still be inefficient. If we check every number as a potential start of a sequence, we end up doing redundant work. For example, in [1, 2, 3, 4], if we start counting from 1, we get a length of 4. Then, if we start counting from 2, we recount [2, 3, 4]. This is wasteful.

The Key Insight: Only Start from the Beginning

The crucial optimization is to only start a sequence count from the true starting point of a sequence. How can we identify a starting point?

A number x is the start of a consecutive sequence if and only if x-1 is not present in the set.

This simple check prevents us from recounting sub-sequences. We will only ever start our while loop (the part that counts the length) for numbers like 1 (because 0 is not present) and 100 (because 99 is not present), but never for 2, 3, or 4.

This video from NeetCode provides an excellent visual intuition for this idea.

3. Algorithm, Implementation, and Complexity

Now that we have the core idea, let's formalize the algorithm and look at its implementation in Java.

Algorithm:

1. If the input array is empty, return 0.
2. Create a HashSet and add all elements from the input array to it.
3. Initialize a variable longestStreak = 0.
4. Iterate through each unique number (num) in the HashSet.
5. For each num, check if set.contains(num - 1).
   • If it does, do nothing and move to the next number. This num is not the start of a sequence.
   • If it does not, then num is the start of a new sequence.
     • Initialize currentNum = num and currentStreak = 1.
     • Enter a while loop that continues as long as set.contains(currentNum + 1).
     • Inside the loop, increment currentNum and currentStreak.
     • After the loop finishes, update longestStreak = Math.max(longestStreak, currentStreak).
6. Return longestStreak.

This approach ensures that the inner while loop (the counting part) is executed only for the starting elements of each consecutive sequence.

Java Implementation

The following article provides a clean, well-commented Java implementation of this algorithm.

Complexity Analysis

• Time Complexity: $O(n)$.

  • Adding n elements to the HashSet takes $O(n)$ time.
  • The outer for loop runs n times (for n unique elements). The inner while loop seems to make it $O(n^2)$, but it's not. Each number is visited by the while loop at most once over the entire execution. The total number of times the while loop's body is executed across all iterations of the outer for loop is at most n. Therefore, the total time is $O(n)+O(n)=O(n)$.

• Space Complexity: $O(n)$.

  • In the worst case (all elements are unique), the HashSet will store all n elements from the input array.

Conclusion

In this lesson, you've learned how to solve the "Longest Consecutive Subsequence" problem optimally using a HashSet. This is a powerful demonstration of how choosing the correct data structure and applying a clever algorithmic trick can lead to significant performance improvements.

Key Takeaways:

• A HashSet is ideal for problems requiring fast checks for the existence of an element.
• The key to optimizing this problem is to avoid redundant work. By only starting a sequence count from a true "start" element (one whose predecessor is not in the set), we reduce the complexity from $O(n\log n)$ or $O(n^2)$ down to $O(n)$.
• Always analyze the time complexity carefully. Loops nested within each other don't automatically mean a polynomial complexity; you must consider how many times the inner loop's body executes in total across all iterations.

Preview of the Next Lesson:
We will be moving on to a new, specialized data structure within the "Hashing and Tries" module: the Trie (also known as a prefix tree). We will learn what a Trie is, how to implement its basic operations like insert and search, and see why it's incredibly efficient for problems involving strings and prefixes, such as implementing an autocomplete feature.