LESSON 226 OF 414 · SORTING

Longest Consecutive Sequence in Scala: 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 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

Guided

Ctrl + Enter to check

Longest Consecutive Sequence in Scala, explained

Problem overview

The method longestConsecutive receives an unsorted array of integers and returns the length of the longest run of consecutive values, such as 1, 2, 3, 4. The values do not have to be next to each other in the array, and each value counts once even if it appears several times.

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, because the run 0, 1, 2, 3 is counted once even though 0, 1 and 2 appear twice.

Approach: sort, then measure each run

In an unsorted array, finding what comes after a value means searching the whole array. After sorting, every run of consecutive numbers becomes one block of neighbouring elements, and the blocks follow each other. The sorted version of the second example is [0, 0, 1, 1, 2, 2, 3], and the whole array is a single block.

Inside a block, each element is one of two things: a duplicate of the run's current last value, or that value plus 1. An element larger than that leaves a gap, so it starts a new run. So the scan keeps currVal, the last value of the current run, and moves a second index forward while the next element is at most currVal + 1. The length of a run is currVal - start + 1, because a run from a to b contains b - a + 1 values. The sort costs O(n log n) and the scan visits each element once, so the total is O(n log n).

Step by step

Start result at 1, as a var. A single element is already a run of length 1, and the value grows when a longer run is found.
Sort nums in place with scala.util.Sorting.quickSort, so runs become contiguous blocks.
Open the outer while loop with an index i that starts at 0. It marks the first element of the run about to be measured. The loop doesn't move i by 1 each time; its last line jumps to where the next run starts.
Start currVal at nums(i). It holds the last value of the current run.
Start j at i + 1, the next element to try to add to the run.
Open the inner while loop: continue while j is inside the array and nums(j) <= currVal + 1. The bounds check comes first, so nums(j) is never read past the end.
Extend the run on the next value. If nums(j) == currVal + 1, add 1 to currVal. A duplicate fails this test and leaves currVal alone.
Advance j on every pass, since duplicates and new values are both consumed.
Record the run's length. After the inner loop, set result to the larger of its old value and currVal - nums(i) + 1.
Jump i to j. Everything before j belongs to the run just measured, and nums(j) is the first element after a gap.
Return result as the final expression.

The solution in Scala

class Solution {
    def longestConsecutive(nums: Array[Int]): Int = {
        var result = 1
        scala.util.Sorting.quickSort(nums)

        var i = 0
        while (i < nums.length) {
            var currVal = nums(i)
            var j = i + 1
            while (j < nums.length && nums(j) <= currVal + 1) {
                if (nums(j) == currVal + 1) {
                    currVal += 1
                }
                j += 1
            }
            result = math.max(result, currVal - nums(i) + 1)
            i = j
        }
        result
    }
}

The Scala details worth knowing:

Why while and not for. A for (i <- 0 until n) loop takes its values from a range and cannot be told to skip ahead. This loop changes i inside its body, so it needs while and a var.
&& short-circuits. If j < nums.length is false, the right-hand side isn't evaluated, so the out-of-range read never happens.
math.max is Scala's wrapper for the same operation as Math.max from Java. Both work on Int values.
No ++. Counters grow with j += 1 and currVal += 1.
The array is sorted in place. quickSort changes the caller's array. nums.sorted would leave it untouched at the cost of a copy.
Last expression. The bare result on the final line is the method's return value.

Complexity

Time: O(n log n). Sorting dominates. The two while loops together move j over each element once: the inner loop advances j, and the outer loop sets i = j rather than rescanning. The scan is O(n).

Space: about O(1) extra, because the sort works in place and the scan keeps a few integers.

Edge cases and common mistakes

Duplicates. [1, 2, 2, 3] gives 3. A duplicate must neither break the run nor be counted twice, which is why the if checks for exactly currVal + 1 while the loop condition allows <= currVal + 1.
Gaps. [1, 2, 4, 5, 6] gives 3: the run 4, 5, 6 starts after the gap.
Negative numbers. [-2, -1, 0, 1] gives 4. Nothing special is needed.
One element. [10] gives 1.
Empty array. The code returns 1, because result starts at 1 and the loop never runs. An array with no elements has no run at all, so the code as written is only right for non-empty input.
Using < instead of <=. The inner loop would accept only duplicates, because an element below currVal + 1 cannot be larger than currVal. The run could never grow, and every input would give 1.
Forgetting i = j. The outer loop never advances and runs forever.
Measuring length as j - i. That counts duplicates. For [0, 0, 1] it gives 3, while the run has 2 distinct values.

Testing

[100, 4, 200, 1, 3, 2] gives 4.
[0, 2, 0, 1, 2, 3, 1] gives 4.
[1, 2, 4, 5, 6] gives 3.
[-2, -1, 0, 1] gives 4.
[10] gives 1.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free