Start learning free

LESSON 203 OF 338 · SORTING

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

    GO · SORTING

    Longest Consecutive Sequence in Go, explained

    Problem overview

    The function longestConsecutive receives an unsorted slice of integers, nums, and returns the length of the longest run of values that follow each other by exactly 1, such as 1, 2, 3, 4. The values don't have to be next to each other in the slice.

    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, from 0, 1, 2, 3. Each value counts once, even when it appears several times.

    The lesson asks for O(n log n) time and O(1) extra space. A hash set would give O(n) time but uses O(n) space.

    Approach: sort, then measure blocks

    After sorting, every run of consecutive values occupies one block of the slice, and the blocks follow one another. Inside a block, each element is either equal to the last value of the run or exactly one larger. A gap of 2 or more starts a new block.

    The scan therefore walks through the sorted slice once. At the start of each block, it remembers the first value, nums[i], and extends the run while the next element is at most currentValue + 1. Duplicates are consumed without growing the run. The length of the block's run is the last value minus the first value, plus 1, because the values from a to b contain b - a + 1 numbers.

    On the sorted second example, [0, 0, 1, 1, 2, 2, 3], the whole slice is one block. The run starts at 0 and reaches 3, so the 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 variable because it grows.
    2. Sort with sort.Ints, which sorts a []int in place.
    3. Set i := 0 and loop with for i < len(nums). Go has no while. A for with only a condition does the same job. The loop doesn't use i++; the last line of its body moves i to where the next block begins.
    4. Record currentValue := nums[i]. It is the last value of the run so far. Since the slice is sorted, remembering this one number is enough.
    5. Set j := i + 1, the next element to try to add.
    6. Run an inner loop while j < len(nums) && nums[j] <= currentValue+1. Such an element is either a duplicate of currentValue or the next value. Anything bigger is a gap, so the block ends. The bounds check comes first so that nums[j] is never read past the end: && stops evaluating as soon as its left side is false.
    7. Extend on the next value. If nums[j] == currentValue+1, increment currentValue. A duplicate fails this test and changes nothing.
    8. Advance j on every pass, for duplicates and new values alike.
    9. Update result with the larger of its value and currentValue-nums[i]+1.
    10. Jump with i = j. Everything before j belongs to the block just measured.
    11. Return result after the outer loop.

    The solution in Go

    func longestConsecutive(nums []int) int {
    result := 1
    sort.Ints(nums)
    i := 0
    for i < len(nums) {
        currentValue := nums[i]
        j := i + 1
        for j < len(nums) && nums[j] <= currentValue+1 {
            if nums[j] == currentValue+1 {
                currentValue++
            }
            j++
        }
        result = max(result, currentValue-nums[i]+1)
        i = j
    }
    return result
}

    Go details:

    • max is a built-in function since Go 1.21, so it needs no import and works on any ordered type. The file does need import "sort".
    • The condition j < len(nums) && nums[j] <= currentValue+1 relies on short-circuit evaluation. Swapping the two operands would panic with an index out of range when j reaches the end.
    • sort.Ints reorders the caller's slice, because slices share their backing array. After calling the function on [3, 1, 2], the caller's slice reads [1 2 3].

    Complexity

    Time: O(n log n). The sort dominates. The two nested loops look quadratic, but j only moves forward and i jumps to j after each block, so every element is passed over once: O(n) for the scan.

    Space: O(1) extra. The function keeps a handful of integers and sorts in place.

    Edge cases and common mistakes

    • Duplicates. [7, 7, 7] returns 1. Counting every element in a block instead of the value range would give 3.
    • Duplicates inside a run. The condition uses <= and not ==, so [1, 2, 2, 3] stays one block and the answer is 3. With ==, the scan would stop at the second 2.
    • A gap. [1, 2, 4] returns 2: the jump from 2 to 4 ends the block.
    • Negative numbers. They work unchanged: [-2, -1, 0, 5, 6] returns 3.
    • An empty slice. The solution returns 1 because result starts at 1 and the loop never runs. The true answer for no values would be 0, so guard against that if empty input is possible.
    • Not moving i forward. If the last line were i++, the same block would be measured again from each of its elements, and the scan would lose its linear cost.

    Try in the editor above: the two examples should both give 4, [5] should give 1 and [1, 2, 4] should give 2.

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