Start learning free

LESSON 222 OF 410 · SORTING

Longest Consecutive Sequence in JavaScript: Sort and Scan

Practice O(n log n) Read the full explanation

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 though 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 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.length).
  • 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

    JAVASCRIPT · SORTING

    Longest Consecutive Sequence in JavaScript, explained

    Problem overview

    The method longestConsecutive(nums) receives an unsorted array of integers and returns the length of the longest run of values that follow each other with no gaps, such as 1, 2, 3, 4. The values do not need to be next to each other in the array, and a repeated value counts once.

    For [100, 4, 200, 1, 3, 2] the longest run is 1, 2, 3, 4, so the answer is 4. For [0, 2, 0, 1, 2, 3, 1] the answer is also 4: the values 0, 1, 2 and 3 each appear at least once, and the duplicates add nothing to the length.

    This lesson allows O(n log n) time and O(1) extra space. The extra budget is what points to sorting.

    Approach: sort, then measure each run

    The difficulty is that consecutive values can be scattered across the array. Sorting removes that problem. After sorting in ascending order, every run of consecutive values sits in one block of the array, and the blocks come one after another. Duplicates end up next to each other, inside the block of their value.

    After [0, 2, 0, 1, 2, 3, 1] is sorted it reads [0, 0, 1, 1, 2, 2, 3]. The whole array is one run from 0 to 3. In a sorted array, a run ends where the gap from one element to the next is larger than 1.

    The scan keeps two indices. i marks where the current run starts, and j moves forward while the next element is still part of the run. When j stops, the run is measured, and the next run starts exactly at j. Each element is visited once, so the scan is O(n) and the sort dominates at O(n log n).

    A faster approach is possible. Put all values in a Set, and start counting only from values x where x - 1 is not in the set. That runs in O(n) time, but it uses O(n) extra space, so it trades memory for speed. The lesson's budget asks for the sorting version.

    Step by step

    1. Start result at 1. A single element is already a run of length 1. The value must be a let variable, because it is updated whenever a longer run is found.
    2. Sort with a comparator. nums.sort((first, second) => first - second) sorts numerically. Without a comparator, JavaScript sorts as strings, so [10, 9, 1].sort() gives [1, 10, 9]. A negative return value puts first before second.
    3. Open an outer while loop on i. It runs while i < nums.length, and it does not add 1 to i each turn. The last line of its body jumps i to the start of the next run.
    4. Remember the run's last value in currVal. It begins as nums[i], since a run starts with one element.
    5. Start j at i + 1. This is the next element to try adding.
    6. Open an inner while loop. It runs while j < nums.length and nums[j] <= currVal + 1. The length test comes first, so nums[j] is never read past the end. In a sorted array, an element that is at most currVal + 1 is either a duplicate of currVal or the next value in the run. Anything bigger is a gap.
    7. Extend the run on the next value. If nums[j] == currVal + 1, increment currVal. A duplicate fails this test and leaves currVal alone, so it is skipped without being counted.
    8. Advance j on every pass, for duplicates and new values alike.
    9. Record the length. After the inner loop, the run goes from nums[i] to currVal, which contains currVal - nums[i] + 1 values. Math.max keeps the larger of that and result.
    10. Set i = j. Everything before j belonged to the run just measured, so the next run starts at j.
    11. Return result after the outer loop.

    The solution in JavaScript

    class Solution {
    
    longestConsecutive(nums) {
        let result = 1;
        nums.sort((first, second) => first - second);
        
        let i = 0;
        while (i < nums.length) {
            let currVal = nums[i];
            let j = i + 1;
            while (j < nums.length && nums[j] <= currVal + 1) {
                if (nums[j] == currVal + 1) {
                    currVal++;
                }
                j++;
            }
            result = Math.max(result, currVal - nums[i] + 1);
            i = j;
        }
        return result;
    }
}

    For the first example, the sorted array is [1, 2, 3, 4, 100, 200]. Starting at i = 0, currVal climbs 1, 2, 3, 4 and j stops at 100, which is bigger than 5. The run length is 4 - 1 + 1 = 4. Then i = 4 gives a run of length 1 for 100, and i = 5 a run of length 1 for 200. The result stays 4.

    JavaScript details

    • sort changes the original array. After the call, the caller's nums is in ascending order. To keep the input intact, sort a copy: [...nums].sort(...). A copy costs O(n) extra space, which is why the lesson sorts in place. Engines may also use temporary memory inside sort, so "O(1)" here means no extra structure of your own.
    • Always pass a comparator for numbers. The default order compares text, which breaks for any numbers with different digit counts.
    • The subtraction comparator is safe here. first - second can lose precision only for numbers near the limits of a double, far beyond the sizes in this problem.

    Complexity

    • Time: O(n log n). The sort costs O(n log n). The two nested while loops look quadratic, but j only moves forward and i jumps to j, so every element is passed over once, O(n) in total.
    • Space: O(1). Only a few variables are added, and the sort is done in place.

    Edge cases and common mistakes

    • Duplicates. [1, 2, 2, 3] has a run of length 3. The duplicate 2 must neither break the run nor be counted twice, which is why the code increments currVal only on currVal + 1.
    • Negative numbers. [-2, -1, 0] returns 3. The formula currVal - nums[i] + 1 works for any integers.
    • A gap exactly at the boundary. [1, 2, 4, 5, 6] returns 3, from 4 to 6. The gap between 2 and 4 is 2, which is larger than 1.
    • The empty array. The code starts result at 1, so an empty array returns 1, not 0. If empty inputs are possible, add if (nums.length === 0) return 0; at the top.
    • Forgetting the comparator. Without it, [9, 10, 11] sorts as strings and the scan sees [10, 11, 9].
    • Counting the elements of the block. j - i counts duplicates too. For [0, 0, 1] it gives 3, but the run has only two distinct values.

    Testing

    • [100, 4, 200, 1, 3, 2] gives 4.
    • [0, 2, 0, 1, 2, 3, 1] gives 4.
    • [5] gives 1.
    • [1, 2, 4, 5, 6] gives 3.
    • [-2, -1, 0] gives 3.
    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free