Longest Consecutive Sequence

mediumFREEHash Maps & SetsApple DSA

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

Input

100,4,200,1,3,2

Output

Reasoning

nums is an unordered list of integers; only which values are present matters, not where they sit. A consecutive sequence is a run of values $v, v+1, \dots, v+k-1$ that all appear in nums, and its length is $k$ .
The sample values are $\{100, 4, 200, 1, 3, 2\}$ . Placed on a number line they form three separate runs: $1, 2, 3, 4$ (length $4$ ), $100$ alone (length $1$ ) and $200$ alone (length $1$ ).
The run $1 \dots 4$ ends where it does because $0$ and $5$ are missing; $100$ is isolated because neither $99$ nor $101$ appears.
The answer is the length of the longest run: the largest of $4, 1, 1$ is $4$ , matching the output 4.
Notice the run's members are scattered through the input, so adjacency in nums is irrelevant. Repeated values count once: the list $0, 3, 7, 2, 5, 8, 4, 6, 0, 1$ holds two zeros, yet its run $0 \dots 8$ has length $9$ . An empty list gives $0$ .

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9

More from Apple DSA

Happy Numbereasy Single Numbereasy Path Sumeasy Invert Binary Treeeasy Maximum Depth of Binary Treeeasy

Concept primer

Background Knowledge

The problem revolves around finding the longest consecutive sequence in an unsorted array of integers. To tackle this, it's essential to understand the concept of a sequence and what makes it consecutive. A sequence is a set of numbers that follow each other in a specific order, and in this case, the order is determined by the numerical value of the elements. A consecutive sequence is one where each element is one more than the previous element.

To solve this problem efficiently, we need to leverage the power of hash maps (or sets), which allow us to store and look up elements in constant time, $O(1)$ . This is crucial because we need to process the array in $O(n)$ time, where $n$ is the number of elements in the array. By using a hash map, we can keep track of the elements we've seen so far and quickly check if an element's predecessor or successor is present in the map.

The problem also requires us to think about how to iterate over the array and update our solution as we encounter new elements. We'll need to consider how to handle duplicates and gaps in the sequence, as well as how to keep track of the longest sequence found so far. These considerations will be essential in designing an efficient algorithm.

Algorithm/Approach

The general approach to solving this problem involves using a hash set to store the elements of the array and then iterating over the set to find the longest consecutive sequence. We'll need to check for each element if its predecessor or successor is present in the set and update our solution accordingly. This approach allows us to take advantage of the fast lookup times provided by the hash set.

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a hash set from the input array to store unique elements.
Initialize variables to keep track of the longest sequence found so far and its length.
Iterate over the hash set and for each element, check if it's the starting point of a sequence (i.e., its predecessor is not in the set).
If it's a starting point, iterate over the sequence and update the longest sequence if necessary.
After iterating over all elements, return the length of the longest sequence found.

Common Pitfalls

When implementing the solution, watch out for:

Duplicates: Make sure to handle duplicate elements correctly, as they should not affect the length of the longest sequence.
Gaps: Be careful when checking for consecutive elements, as gaps in the sequence can lead to incorrect results.
Edge cases: Consider edge cases, such as an empty input array or an array with a single element.

Time & Space Complexity

The expected time complexity for this problem is $O(n)$ , where $n$ is the number of elements in the input array. This is because we need to process each element at least once. The space complexity is also $O(n)$ , as in the worst case, we might need to store all elements in the hash set.

solution.py

Python 3.13

Test results