DEV Community

Ashley Nguyen
Ashley Nguyen

Posted on

LeetCode #128 - Longest Consecutive Sequence

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

_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

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

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

Final code (after rearrange if else statements):

Image description

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

Heroku

Built for developers, by developers.

Whether you're building a simple prototype or a business-critical product, Heroku's fully-managed platform gives you the simplest path to delivering apps quickly — using the tools and languages you already love!

Learn More

Top comments (0)

Jetbrains image

Build Secure, Ship Fast

Discover best practices to secure CI/CD without slowing down your pipeline.

Read more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay