128. Longest Consecutive Sequence
Problem
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:
Example 2:
Example 3:
Constraints:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
Approach
We can start by creating a hashmap to store which numbers occur in the array. After this, we iterate over the numbers. For each number, we check if the value one less than it occurs in the array via the hashmap. If it doesn't, we know we are the start of a sequence. Once we know we are at the start of a sequence, we iterate as long as there is a value exactly one more than that in the array, keep track of the count. We update the max value with this count.
Edge Cases
The first edge case is when there are no values in the array, we want to simply return 0.
The next edge case occurs with the time complexity. If there are duplicates of the start of a sequence, without proper handling, we'll run unnecessary iterations. For example, if a sequence starts with 0 and has a length of 100, and we have two zeroes in the array, we'll run that 100 length iteration twice. To mitigate this, we want to mark in the hash map if the start of a sequence has already been processed and check for that mark before iterating over the sequence and override it.
In our case, we do this by marking with a boolean value in the hashmap since we are using a boolean map.
Complexity
Time: O(n)
It might look like it's not O(n) because we have a nested loop, however, there is an important consideration. We only go down that nested loop if it's the start of a sequence, otherwise, we keep marching forward. Therefore, in the worst case, when all values are consecutive, we only go down the nested loop once, maintaining O(n)
Space: O(n)
We create a hashmap of size n.