Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Example 1:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: Longest consecutive sequence is [1, 2, 3, 4].
Therefore its length is 4.
Example 2:
Input: [0, 2, 0, 1, 2, 3, 1]
Output: 4
Explanation: Longest consecutive sequence is [0, 1, 2, 3].
Therefore its length is 4.
Note that we count each value once, even tho values 0, 1 and 2 appear 2 times each in nums
Note:
For this lesson, your algorithm should run in O(n log n) time and use O(1) extra space.
(There are faster solutions which we will discuss in future lessons)
Hints:
Let's sort the array in non-decreasing order. In this way each consecutive elements sequence is a subarray of the sorted array. Even more, these consecutive elements subarrays will come one after another.
Let's start by finding the first subarray. Its left endpoint is
i = 0. We will use another index variable j to find the right endpoint. j is initially equal to 0 and should be incremented for as long as nums[i...j] is a consectuive subarray. But how can we check this?
j is initially equal to 0 and will be incremented as long as nums[j] <= nums[j - 1] + 1. When the condition is not satisfied anymore, we have found the first subarray: nums[i...j-1]. How can we find the second one?
The leftpoint of the second subarray is
j. So we can set the index i to j. Then we can continuously increment j as long as our condition is satisfied just like we did for the first subarray. When the condition is not satisfied anymore, we have found the second subarray: nums[i...j-1]. Can we use the same strategy for finding the rest of the subarrays?
Yes, we can. We should design an algorithm that repeats this strategy until we are left with no more subarrays (e.g.
i >= n).
- 1. Initialize
iwith0. - 2. While
i < n: -
- 1. Initialize
jwithi + 1. - 2. While
nums[j] <= nums[j - 1] + 1, incrementj - 3. Set
itojand return to step 1.
- 1. Initialize
Walkthroughs of the solution. Try the steps first, then watch to compare approaches.
Solution #1 · O(n log n)
Free plan: 30 tutor messages. Premium is unlimited.
Saved
Ctrl + Enter to check