Start learning free

LESSON 301 OF 667 · SORTING

Longest Consecutive Sequence

Practice O(n log n)

You get a vector nums of integers, in no particular order.

Return the length of the longest run of consecutive values.

Consecutive values go up by 1 each time. For example, 5, 6 and 7 form a run of length 3.

The values of a run can be anywhere in nums. A value that appears more than once counts only once.

Example 1:

Input: nums = [9, 13, 10, 5, 11, 6]
Output: 3
Explanation: 9, 10 and 11 make the longest run.
5 and 6 make a shorter run.
13 stands alone.

Example 2:

Input: nums = [-2, 0, -1, 0, 2, -1]
Output: 3
Explanation: The longest run is -2, -1 and 0.
0 and -1 appear twice, but each counts once.
2 is not in the run, because 1 is missing.

Example 3:

Input: nums = [40, 10, 30, 20]
Output: 1
Explanation: No two values are 1 apart.
So every run has just one value.

Constraints:

  • nums has 1 to 30,000 integers.
  • Each value is from -100 to 100,000,000.

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 i + 1 and should be incremented for as long as nums[i...j] is a consecutive subarray. But how can we check this?

j is initially equal to i + 1 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 left endpoint 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, where n is nums.size()).
  • 1. Initialize i with 0.
  • 2. While i < n:
    • 1. Initialize j with i + 1.
    • 2. While nums[j] <= nums[j - 1] + 1, increment j
    • 3. Set i to j and return to step 1.

STEP 1 OF 11
    Ctrl + Enter to check