Start learning free

LESSON 229 OF 414 · SORTING

Longest Consecutive Sequence in Rust: 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.len()).
  • 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

    RUST · SORTING

    Longest Consecutive Sequence in Rust, explained

    Problem overview

    The function longest_consecutive receives an unsorted vector of integers, nums, and returns the length of the longest run of consecutive values, such as 1, 2, 3, 4. The values don't have to be neighbours in the input, and repeated values count once.

    For nums = [100, 4, 200, 1, 3, 2] the values 1, 2, 3 and 4 form a run of length 4, so the answer is 4. For [0, 2, 0, 1, 2, 3, 1] the answer is also 4: the run is 0, 1, 2, 3, and the repeated 0, 1 and 2 are counted once each. An empty vector gives 0.

    The lesson asks for O(n log n) time and O(1) extra space.

    Approach: sort, then measure each block

    In an unsorted vector, finding the neighbours of a value means searching for it. After sorting, a run of consecutive values becomes a block of adjacent elements, and different runs follow one after another. The sorted form of the second example is:

    [0, 0, 1, 1, 2, 2, 3]

    One pass over the sorted vector can then measure each block. For a block that starts at index i, keep curr_val, the last value of the run so far, and scan forward with j. The next element nums[j] falls into one of three cases:

    • It equals curr_val: a duplicate. The run doesn't grow, but it doesn't end either.
    • It equals curr_val + 1: the run grows by one value.
    • It is larger than curr_val + 1: there is a gap, and the run is over.

    Since the vector is sorted, nothing can be smaller than curr_val. When the run ends at j, its length is the distance between its first and last values plus one, curr_val - nums[i] + 1. Counting by values and not by elements is what makes duplicates harmless. The next run starts at j, so i jumps there. Every element is passed over once, so the scan is O(n) and the sort dominates.

    The first example sorts to [1, 2, 3, 4, 100, 200]. The first block starts at 1 and grows to 4, giving length 4. At 100 there is a gap, so 100 alone is a run of 1, and 200 is another run of 1.

    Step by step

    1. Sort nums in place with sort_unstable(). The starting code already returns 0 for an empty vector and rebinds nums as mutable. Order among equal integers doesn't matter, so the unstable sort is fine.
    2. Start result at 1. It is a mutable i32. A single element is already a run of length 1.
    3. Open the outer loop. The index i is a mutable usize starting at 0. The loop runs while i < nums.len(), and i marks the first element of the run to measure. The loop doesn't add 1 to i: its last line jumps it to where the next run starts.
    4. Remember the last value. curr_val starts as nums[i]. After sorting, a run is one block, so its last value is enough to decide whether the next element belongs.
    5. Create the scan index. j starts at i + 1, the next element to try.
    6. Open the inner loop. It runs while j < nums.len() and nums[j] <= curr_val + 1. Such an element is a duplicate or the next value; anything larger is a gap. The bounds check goes first, so nums[j] is never read past the end.
    7. Grow on the next value. If nums[j] == curr_val + 1, add 1 to curr_val. A duplicate leaves it unchanged.
    8. Advance j by one on every pass, for duplicates and new values alike.
    9. Record the length. After the inner loop, set result to the larger of itself and curr_val - nums[i] + 1.
    10. Jump to the next run by setting i = j. Everything before j belonged to the run just measured.
    11. Return result as the last expression.

    The solution in Rust

    impl Solution {
    fn longest_consecutive(nums: Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }
        let mut nums = nums;
        nums.sort_unstable();
        let mut result = 1i32;
        let mut i = 0usize;
        while i < nums.len() {
            let mut curr_val = nums[i];
            let mut j = i + 1;
            while j < nums.len() && nums[j] <= curr_val + 1 {
                if nums[j] == curr_val + 1 {
                    curr_val += 1;
                }
                j += 1;
            }
            result = result.max(curr_val - nums[i] + 1);
            i = j;
        }
        result
    }
}

    The Rust details worth a closer look:

    • Literal suffixes. 1i32 and 0usize fix the types of result and i. The first must match the return type, and the second must be usize to index a vector.
    • Short-circuit &&. In j < nums.len() && nums[j] <= curr_val + 1, the right side runs only if the left side is true. That is what keeps nums[j] in bounds.
    • while and manual indices. Because i jumps by a variable amount, a for range doesn't fit, so the code uses while with i = j.
    • max is a method. result.max(...) returns the larger of two i32 values.
    • Overflow at the edge. The lessons build with optimizations, where i32 overflow wraps silently, and a debug build would panic instead. With curr_val equal to i32::MAX, the expression curr_val + 1 wraps to i32::MIN. In an optimized build, the input [2147483646, 2147483647, 2147483647] still returns 2, because the wrapped bound only stops the scan one step early, and the leftover duplicate forms a run of its own.

    Complexity

    Time: O(n log n). The sort takes O(n log n). The two nested while loops look quadratic, but j only moves forward and i is set to j after each block, so every element is visited once in total: O(n).

    Space. The scan uses a few integers. The sort is in place, and sort_unstable() needs no temporary buffer, so the extra space is O(1).

    Edge cases and common mistakes

    • Empty vector. The first guard returns 0. Without it, the starting value of 1 would be wrong.
    • Duplicates. They must neither end a run nor lengthen it. For [1, 2, 2, 3] the answer is 3, not 4. That is why the length comes from curr_val - nums[i] + 1 and not from the number of elements scanned.
    • Counting elements instead of values. Using j - i as the length gives the number of elements in the block, which includes duplicates. For [0, 2, 0, 1, 2, 3, 1] that would be 7.
    • Using < instead of <=. The condition nums[j] < curr_val + 1 accepts only duplicates, so the run never grows.
    • Negative numbers. Runs such as -2, -1, 0 work like any others. For [-2, -1, 0, 3, 4] the answer is 3.
    • A gap in the middle. For [1, 2, 2, 3, 10, 11, 12, 13] the runs have lengths 3 and 4, and the answer is 4.

    Testing

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