Start learning free

LESSON 231 OF 414 · SORTING

Find Second Largest in Rust: Sort in Descending Order

Practice O(n log n) Read the full explanation

Given an array of integers, return the second largest value.

Example:

Input: nums = [2, 7, 11, 8, 11, 8, 3, 11]
Output: 8
Explanation: The maximum value is 11. The second largest value is 8.

Note:

You may assume the array contains at least two distinct values.


Follow up:

Could you solve this in one pass without sorting?


STEP 1 OF 5
    Ctrl + Enter to check

    RUST · SORTING

    Find Second Largest in Rust, explained

    Problem overview

    The function second_largest takes a vector of integers, nums, and returns the second largest value. Duplicates of the maximum don't count as the second largest: it is the biggest value that is strictly smaller than the maximum. The array is guaranteed to hold at least two distinct values.

    In the example, nums = [2, 7, 11, 8, 11, 8, 3, 11]. The maximum is 11, and it appears three times. The largest value below it is 8, so the answer is 8, not 11.

    Approach: sort, then skip the maximum

    If the vector is sorted from largest to smallest, the maximum sits at index 0, and every copy of it sits right next to it. Walk from the left and the first value that differs from nums[0] is the second largest. Because the guarantee says there are two distinct values, that value always exists.

    For the example, the descending order is [11, 11, 11, 8, 8, 7, 3, 2]. The first three values equal 11 and are skipped, and the fourth is 8.

    Taking nums[1] after sorting is the classic mistake. With duplicates of the maximum, that gives 11 here. Comparing against the maximum is what handles the duplicates.

    Sorting costs O(n log n). The follow-up asks whether one pass without sorting is possible, and it is; a short version appears below. This lesson takes the simpler route.

    Step by step

    1. Sort in descending order. sort_by takes a closure that compares two elements. Comparing b with a instead of a with b reverses the order.
    2. Loop over a reference to the vector. Writing &nums borrows the vector instead of moving it into the loop, so nums[0] stays usable inside the body.
    3. Skip the maximum. Each num is a &i32, so it is dereferenced with * before the comparison with nums[0], which is an i32.
    4. Return the first different value. It is the largest one below the maximum, because the vector is in descending order.
    5. Add a fallback return of -1. The compiler requires every path to produce an i32. The guarantee means the line never runs.

    The solution in Rust

    impl Solution {
    fn second_largest(mut nums: Vec<i32>) -> i32 {
        nums.sort_by(|a, b| b.cmp(a));
        for num in &nums {
            if *num != nums[0] {
                return *num;
            }
        }
        return -1;
    }
}

    The Rust details worth a closer look:

    • mut nums. The parameter takes ownership of the vector, and sorting changes it in place, so the binding must be mut. The caller's vector isn't affected because it was moved in.
    • The comparator. sort_by hands the closure two references, a and b. b.cmp(a) returns an Ordering, and swapping the operands gives descending order. Calling sort() and then reading from the end would give the same result without a closure.
    • References in the loop. for num in &nums yields &i32. Comparing a &i32 with an i32 doesn't compile, which is why the lesson writes *num. Returning *num copies the integer out of the vector.
    • Borrowing and indexing together. The loop holds a shared borrow of nums, and nums[0] only reads, so the two don't conflict. Pushing to nums inside the loop would be rejected.
    • return -1; at the end. It is legal here, although the idiomatic form is a bare -1 without return and without a semicolon.

    The one-pass follow-up

    Two variables are enough: largest and second, both starting at i32::MIN. For each value x, a value above largest pushes the old maximum down to second. A value strictly between the two replaces second. A value equal to largest changes nothing, which is how duplicates are skipped.

    fn one_pass(nums: &[i32]) -> i32 {
    let mut largest = i32::MIN;
    let mut second = i32::MIN;
    for &x in nums {
        if x > largest {
            second = largest;
            largest = x;
        } else if x < largest && x > second {
            second = x;
        }
    }
    second
}

    On the example it returns 8. It runs in O(n) time with O(1) extra space.

    Complexity

    Time: O(n log n). The sort dominates. The loop that follows visits at most n elements, and usually stops after the duplicates of the maximum.

    Space: O(1) extra. The vector is sorted in place, and the loop adds no collections. Rust's stable sort_by may use a temporary buffer of up to n elements internally.

    Edge cases and common mistakes

    • Duplicates of the maximum. [5, 5, 4] gives 4. Reading index 1 of the sorted vector would return 5.
    • Negative numbers. [-1, -2, -2] gives -2. Nothing in the approach assumes positive values, so don't start a running maximum at 0 in the one-pass version.
    • Only two distinct values. [1, 9, 9, 1] gives 1, the smaller value, found after the 9s.
    • All values equal. [1, 1, 1] breaks the guarantee, and the function returns the -1 fallback. Don't rely on it as a real answer, since -1 can itself be an element.
    • Ascending order. Using sort() alone puts the maximum at the end, so the comparison with nums[0] would test against the minimum.

    Testing

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