Start learning free

LESSON 203 OF 348 · SORTING

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

    KOTLIN · SORTING

    Longest Consecutive Sequence in Kotlin, explained

    Problem overview

    Given an unsorted IntArray named nums, longestConsecutive returns the length of the longest run of values that increase by exactly 1, such as 1, 2, 3, 4. The values don't have to be next to each other in the input.

    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 (0, 1, 2, 3): each value counts once, even though 0, 1 and 2 appear twice.

    Approach

    The brute-force idea is to start from each value and keep checking whether the next value exists somewhere in the array. Searching an unsorted array each time makes that O(n^2) or worse. A hash set can answer "does this value exist?" in constant time, but this lesson wants O(n log n) time with O(1) extra space, so it sorts instead.

    After sorting, every consecutive run is a contiguous block of the array, and the blocks follow one another. Inside a block, each element is either the same as the previous one (a duplicate) or exactly one larger. A gap of 2 or more means the block has ended and the next one starts. So one left-to-right scan can measure every block, and we keep the longest.

    Sorted, the second example is [0, 0, 1, 1, 2, 2, 3]. There is a single block from 0 to 3, so the answer is 3 - 0 + 1 = 4.

    Tracing [100, 4, 200, 1, 3, 2] after sorting, [1, 2, 3, 4, 100, 200]: the first block starts at 1, currVal climbs to 4, and the result becomes 4. The scan then stops at 100 because it is more than 5, and each of 100 and 200 forms a block of length 1.

    Step by step

    1. Create result as a var starting at 1. Any non-empty array contains a run of length 1, and the value grows as longer runs are found.
    2. Sort nums in place with sort().
    3. Create the index i at 0 and open a while loop that runs while i < nums.size. Here i is the first element of the run being measured. The loop doesn't add 1 to i at the end; the last line of its body jumps it to the start of the next run.
    4. Create currVal as a var equal to nums[i]. It is the last value of the run so far.
    5. Create j equal to i + 1, the next element to try.
    6. Open an inner while with the condition j < nums.size && nums[j] <= currVal + 1. Because the array is sorted, an element that passes is either a duplicate of currVal or the next value. Anything bigger is a gap. The length check comes first so nums[j] is never read past the end.
    7. Extend the run if it is the next value. If nums[j] == currVal + 1, increment currVal. A duplicate fails this test and leaves currVal unchanged, so it isn't counted twice.
    8. Increment j on every pass, whether the element was a duplicate or a new value.
    9. After the inner loop, update result with maxOf(result, currVal - nums[i] + 1). A run from a to b contains b - a + 1 values.
    10. Set i = j. Everything before j belongs to the run just measured, so the next run begins at j.
    11. Return result.

    The solution in Kotlin

    class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        var result = 1
        nums.sort()

        var i = 0
        while (i < nums.size) {
            var currVal = nums[i]
            var j = i + 1
            while (j < nums.size && nums[j] <= currVal + 1) {
                if (nums[j] == currVal + 1) {
                    currVal++
                }
                j++
            }
            result = maxOf(result, currVal - nums[i] + 1)
            i = j
        }
        return result
    }
}

    Kotlin details worth knowing:

    • Kotlin has no C-style for (i = 0; ...; ...) loop, and here i jumps by variable amounts, so a while loop is the natural fit.
    • && stops as soon as its left side is false. That's why j < nums.size protects the read of nums[j].
    • maxOf(a, b) is a built-in function that returns the larger of two values.
    • currVal++ works on a var. Writing val currVal would be a compile error.
    • An Int is 32 bits. The expression currVal + 1 would wrap around if currVal were Int.MAX_VALUE, which can only matter for inputs at the very limit of the type.

    Complexity

    • Time: O(n log n) for the sort. The two nested loops look quadratic, but j only moves forward and i is set to j after each block, so every element is visited once: O(n). The sort dominates.
    • Space: O(1) extra, since only a few variables are added and the sort works in place.

    Edge cases and common mistakes

    • Duplicates. They must neither end a run nor lengthen it. That's the reason for the two-part test: <= in the loop condition and == before incrementing.
    • Using == in the loop condition. nums[j] == currVal + 1 would stop the scan at the first duplicate, so [1, 2, 2, 3] would give 2 instead of 3.
    • Measuring length as j - i. That counts duplicates. For [1, 2, 2, 3] it gives 4, but the answer is 3.
    • Negative numbers. They work without changes: [-2, -1, 0] gives 3.
    • All values equal. [5, 5, 5] gives 1.
    • Reading past the end. Putting nums[j] <= currVal + 1 before the length check throws an ArrayIndexOutOfBoundsException when j reaches nums.size.
    • Empty array. The loop is skipped and the function returns 1, although the true answer is 0. If empty inputs are possible, return 0 first.

    Testing

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