Start learning free

LESSON 203 OF 348 · SORTING

Longest Consecutive Sequence in TypeScript: O(n log n) with Sorting

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

    TYPESCRIPT · SORTING

    Longest Consecutive Sequence in TypeScript, explained

    Problem overview

    The method longestConsecutive receives an unsorted array of integers, nums, and returns the length of the longest run of consecutive values: numbers that follow each other with a gap of exactly 1, such as 1, 2, 3, 4. The numbers don't have to be next to each other in the array.

    In the first example, [100, 4, 200, 1, 3, 2], the values 1, 2, 3 and 4 form a run of length 4, while 100 and 200 are alone. The answer is 4.

    In the second example, [0, 2, 0, 1, 2, 3, 1], the run is 0, 1, 2, 3, and the answer is again 4. Duplicates don't make the run longer: each value counts once, even though 0, 1 and 2 appear twice.

    The statement sets a budget of O(n log n) time and O(1) extra space. Faster solutions exist, but they need extra memory.

    Approach: sort, then measure each block

    In the original order, finding what comes after a value means searching the whole array. After sorting in ascending order, every run of consecutive values is a contiguous block of the array, and the blocks follow one another. The only complication is duplicates, which sit inside a block: [0, 0, 1, 1, 2, 2, 3] is one run of length 4 in seven elements.

    So the plan is to scan the sorted array once. At the start of each block, remember the first value and keep extending the block while the next element is either a duplicate of the last value or exactly one more. A larger gap ends the block, and the next block starts there. The length of a block is its last value minus its first value, plus 1.

    Take the second example. The sorted array is [0, 0, 1, 1, 2, 2, 3]. The block starts at 0, and currVal is 0. The second 0 is a duplicate, so it is skipped. Then 1 raises currVal to 1, the second 1 is skipped, 2 raises it to 2, the second 2 is skipped, and 3 raises it to 3. The block ends at the end of the array, and its length is 3 - 0 + 1 = 4.

    Step by step

    1. Start result at 1. A single element is already a run of length 1. It is a let variable because it grows when a longer run is found.
    2. Sort nums with a comparator returning first - second, so values go in ascending order. Without it, the numbers would be compared as strings and 10 would come before 9.
    3. Use an index i that marks the start of a block, and loop while i < nums.length. The loop doesn't add 1 to i; the last line of its body jumps to where the next block starts.
    4. Set currVal to nums[i]. It holds the last value of the current run, which at the start is just the first one.
    5. Let j scan forward from i + 1.
    6. Extend while the block continues. The inner loop runs while j is inside the array and nums[j] <= currVal + 1. Because the array is sorted, such an element is either a duplicate of currVal or the next value. Anything larger means a gap. The j check comes first, so nums[j] is never read past the end.
    7. Grow the run only on the next value. If nums[j] === currVal + 1, increment currVal. A duplicate fails this check and leaves it alone.
    8. Advance j on every pass, whether the element was a duplicate or a new value.
    9. Record the length with Math.max(result, currVal - nums[i] + 1).
    10. Jump to the next block with i = j: everything before j belonged to the block just measured.
    11. Return result after the outer loop.

    The solution in TypeScript

    class Solution {
    longestConsecutive(nums: number[]): number {
        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;
    }
}

    Details worth knowing:

    • Short-circuit &&. When j < nums.length is false, the right side isn't evaluated. Reading past the end of an array in TypeScript doesn't throw; it gives undefined, and undefined <= 5 is simply false. The check is still worth keeping, because it states the intent.
    • Strict equality. === compares two numbers without any conversion, which is what you want here.
    • Math.max takes any number of arguments and returns the largest one.
    • Sorting changes the caller's array. That keeps the extra space at O(1). To keep the original, sort a copy with [...nums].
    • No integer overflow worry. number is a double, and values near the limits of 32-bit integers are still exact. Beyond 2^53, integers start losing precision, which isn't a concern for this lesson's inputs.

    Complexity

    Time: O(n log n). The sort costs O(n log n). In the scan, j only moves forward and the outer loop continues from j, so each element is visited once by the inner loop. That makes the scan O(n), and the sort dominates.

    Space: O(1). The code uses a handful of variables, and the sort works in place.

    Edge cases and common mistakes

    • Duplicates. [5, 5, 5] returns 1: the duplicates fail the === currVal + 1 check, so the run stays at one value.
    • A gap. [1, 2, 4, 5, 6] returns 3, from the block 4, 5, 6.
    • Negative numbers. [-2, -1, 0] returns 3. The length formula uses a difference, so signs don't matter.
    • An empty array. This code returns 1, because result starts at 1 and the loops never run. The lesson's inputs have at least one element; if empty input were allowed, the answer should be 0 and the method would need a check first.
    • Counting duplicates twice. Incrementing currVal for every element in range would turn [0, 0, 1] into a run of 3 instead of 2.
    • Forgetting the comparator. With default string order, [9, 10, 11] sorts as [10, 11, 9] and the run is found as 2 instead of 3.

    Testing

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