Start learning free

LESSON 357 OF 414 · GREEDY

Find Second Largest in Rust: One Pass, No Sorting

Practice O(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 7
    Ctrl + Enter to check

    RUST · GREEDY

    Find Second Largest in Rust, explained

    Problem overview

    The function second_largest receives a vector of integers, nums, and returns the second largest value. Duplicates of the maximum don't count as the runner-up. You may assume the vector holds at least two distinct values.

    For nums = [2, 7, 11, 8, 11, 8, 3, 11] the maximum is 11, which appears three times. The largest value that is different from 11 is 8, so the answer is 8.

    Approach: two trackers in a single pass

    The simple way is to sort the vector and walk back from the end until a value differs from the last one. That costs O(n log n). You can also scan twice: once to find the maximum, and once to find the largest value below it.

    In Rust the sorting version is short. dedup removes consecutive repeats, which after a sort means all repeats:

    fn second_by_sort(nums: Vec<i32>) -> i32 {
    let mut v = nums;
    v.sort_unstable();
    v.dedup();
    v[v.len() - 2]
}

    For [2, 7, 11, 8, 11, 8, 3, 11] it also returns 8. It allocates nothing extra, but it reorders the data and does more work than the question needs, since only the top two values matter.

    A single scan is enough if you keep two variables, the best value so far (max_val) and the best value strictly below it (second). For each number there are three cases:

    • It is larger than max_val. The old maximum becomes the runner-up and the number becomes the new maximum.
    • It is smaller than max_val but larger than second. It is a better runner-up.
    • Anything else, including a repeat of the current maximum, changes nothing.

    On the example, the trackers move like this: after 2 they are (2, MIN), after 7 (7, 2), after 11 (11, 7), then 8 becomes the runner-up (11, 8). The later 11s, 8s and 3 change nothing, so the result is 8.

    The "old maximum becomes the runner-up" move is correct because the old maximum was larger than everything seen before it, and the new number is larger than the old maximum. So the old maximum is the largest value below the new maximum among everything seen so far.

    Step by step

    1. Declare max_val and second with let mut, both set to i32::MIN. Every real value is at least that large, so the first elements always take over without a special "first iteration" check.
    2. Loop over the vector with for num in nums, so every element gets a chance to update the trackers.
    3. Test for a new maximum with if num > max_val.
    4. Demote the old maximum before overwriting it. Copy max_val into second first, then store num in max_val. Swapping those two lines would lose the old maximum.
    5. Add an else if for a number that is strictly less than max_val and strictly greater than second. The strict comparison with max_val is what keeps duplicates of the maximum from becoming the runner-up.
    6. Update second in that branch.
    7. Return second.

    The solution in Rust

    impl Solution {
    fn second_largest(nums: Vec<i32>) -> i32 {
        let mut max_val = i32::MIN;
        let mut second = i32::MIN;
        for num in nums {
            if num > max_val {
                second = max_val;
                max_val = num;
            } else if num < max_val && num > second {
                second = num;
            }
        }
        return second;
    }
}

    The Rust details worth a closer look:

    • i32::MIN is the smallest 32-bit signed integer, -2147483648, an associated constant of the type.
    • Iterating by value. for num in nums consumes the vector and gives each element as a plain i32, so comparisons need no dereferencing. The vector can't be used after the loop, which is fine here because the function only returns a number.
    • return second; is an explicit return. Writing second as the last expression, without a semicolon and without return, does the same thing.
    • Mutability. Both trackers are reassigned inside the loop, so both need mut.

    Complexity

    Time: O(n). One pass, with a constant number of comparisons per element.

    Space: O(1). Two integers, whatever the length of the vector.

    The sorting version takes O(n log n) time, so the single pass is the better answer to the follow-up question. Both are correct on every valid input, and the one-pass loop never needs to look at an element twice.

    Edge cases and common mistakes

    • Duplicates of the maximum. In [7, 7, 3] the answer is 3. If the comparison were num <= max_val, the second 7 would become the runner-up.
    • Increasing and decreasing input. [1, 2, 3, 4, 5] and [5, 4, 3, 2, 1] both return 4. The first order exercises the demotion branch on every element, the second the else if branch.
    • Two elements. [5, 9] and [9, 5] both return 5.
    • Negative numbers. [-5, -5, -7] returns -7. Starting the trackers at 0 instead of i32::MIN would wrongly return 0.
    • Wrong order of the two assignments. Setting max_val = num first and then second = max_val makes both trackers equal to num.
    • Fewer than two distinct values. For [4, 4, 4] the function returns i32::MIN, because second never changes. The lesson rules this input out.

    Testing

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