A medium LeetCode problem after days of only easy or no LeetCode at all. I got all test cases passed after four trials (the time gaps were due to my dinner..), and all of them were necessary to solve my careless presumptions in understanding the problem - really reminding me to spend more time thoroughly digging into edge cases and the underlying purpose.
_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.
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
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
_
Understand the problem
The problem statement was quite straightforward (poor assumption!) and the given examples made it even more self-explanatory: we need to find out in the given array the longest sequence that contains consecutive numbers. It looks to me that we can sort the array for this question and then it becomes much easier: all we need to do left is to identify the longest subarray that contains consecutive integers.
What about edge cases? In the case that the array is empty or has only one element, the result will be the length of the array itself.
**Match the problem
One thing I could think of in the first place after sorting the array is that there can be multiple relevant subarrays in the sorted array. Therefore, we need to find all those subarrays, keep a variable that represent the subarray length, and keep updating the variable whenever we find a longer relevant sequence. This sounded to me like a sliding window problem.
The first thing to do after handling the edge case and sorting the array is creating two variables representing the start and end of the sliding window. I declare them both at 0.
One question at this point might be: Why do we declare maxLen at 1, not 0 or any other number? The reason is that we can consider each integer a relevant sequence to return; therefore, even if the array does not contain any more than 2-integer relevant sequence, the result returned will always be 1.
Another question is : Why don't we declare left at 0 and right at 1 - we need to compare two consecutive numbers, don't we? The answer is that we will not use both left and right variables to compare, but the left variable will rather be "static" while the right variable continues to increment in case we identify a possible relevant sequence.
The right variable is actually compared to its next [right + 1]. If their difference is 0, we continue to increment right and keep an eye for maxLen. If otherwise, that means we need to start considering a new sequence starting at where right currently is, so we summon left to represent the start of a new sequence.
BUT ...
One case I did not encounter for is.. what if the sorted array looks like this: [0,1,1,2]. The answer for this case should be 3, not 2, because the problem is not asking for a sequence of consecutive numbers that lie next to each other, but that the numbers only need to be in the array. So in case there is duplicates, we can simply count them as one and move on.
Final code (after rearrange if else statements):
The time complexity of Arrays.sort is O(nlogn), and the time complexity of the rest of the code is O(n) (since we iterate through all elements). Therefore the overall time complexity is O(nlogn).
Top comments (0)