LeetCode #128 - Longest Consecutive Sequence
Published: 2023-06-08 17:44:40

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. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5hj939vlpr6w86bmn8rr.png)

_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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/saoq09jtl8avmpbrp1zf.png)

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. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1fq91uvcuf8h7es1i9lq.png)

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iw6wln5w08b12gkqs9ty.png)

Final code (after rearrange if else statements): 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/won6pt6yt3llc1p3eqbi.png)

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).