LESSON 93 OF 414 · CONDITIONAL STATEMENTS - CHALLENGES

Second Largest of Three Numbers in Rust: O(1) with min and max

Given 3 integers (the parameters A, B and C; Rust and Go name them in lowercase), return the second largest number.

Example 1:

Input: A = 7, B = 3, C = 9
Output: 7

Example 2:

Input: A = 12, B = 8, C = 3
Output: 8

Note:

Your algorithm should run in O(1) time and use O(1) extra space.

Hints:

There are three candidates to the solution: A, B and C. We should try out each of them until we find the correct one. How can we check if A is the solution? What should happen for A to be the second largest value?

A is the second largest value if the smaller of B and C is less than or equal to A, and A is less than or equal to the larger of B and C. We can write an if statement checking these two conditions and, if they hold, return A. What if the conditions don't hold and A is not the solution? What should we do next?

We should test B. Similarly, B is the second largest value if the smaller of A and C is less than or equal to B, and B is less than or equal to the larger of A and C. We can write a second if statement checking these conditions and, if they hold, return B. What if not even B is the solution?

Then, it's clear that C is the solution, so we should return C. We don't even need to check the conditions anymore.

STEP 1 OF 3

Guided

Ctrl + Enter to check

Second Largest Value in Rust, explained

Problem overview

The function second_largest receives three i32 values, a, b and c, and returns the middle one when they are ordered by size. For 7, 3, 9 the sorted order is 3, 7, 9, so the answer is 7. For 12, 8, 3 the answer is 8. The lesson asks for O(1) time and space, so the function can't sort a collection or loop.

Approach

The answer is always one of the three inputs, so test them one at a time. A number is the second largest, the middle one, when it is at least the smaller of the other two and at most the larger of the other two. For a that reads b.min(c) <= a && a <= b.max(c).

Check a, then b. If neither is in the middle, c must be, so there is no need to test it.

Take a = 7, b = 3, c = 9. The smaller of b and c is 3 and the larger is 9. Since 3 <= 7 <= 9, the function returns 7 immediately. With a = 12, b = 8, c = 3, the test for a compares against 3 and 8: 12 is above 8, so it fails. The test for b compares against 3 and 12: 3 <= 8 <= 12 holds, so it returns 8.

Step by step

Test a. The condition has two parts joined with &&: b.min(c) <= a and a <= b.max(c). If both hold, return a. The parameters are the lowercase a, b and c.
Test b. The same idea with the roles changed: a.min(c) <= b and b <= a.max(c). If both hold, return b.
Return c. At this point neither a nor b is the middle value, so c is. Write it as the function's final expression, with no semicolon.

The solution in Rust

impl Solution {
    fn second_largest(a: i32, b: i32, c: i32) -> i32 {
        if b.min(c) <= a && a <= b.max(c) {
            return a;
        }
        if a.min(c) <= b && b <= a.max(c) {
            return b;
        }
        c
    }
}

Rust details worth knowing:

min and max are methods. Rust has no global min(x, y) function in the prelude. You call the method on one value and pass the other: b.min(c) is the smaller of b and c. Both values must have the same type, here i32.
Final expression. The last line is c with no semicolon and no return. A block's last expression, when not followed by a semicolon, is its value, which is how Rust functions normally return. Writing c; instead turns it into a statement, the function then returns () and the compiler reports mismatched types.
Early return. The two return lines leave the function at once, so later lines run only when the earlier tests failed. This is why no else is needed.
Precedence. Comparisons bind tighter than &&, so the parts of each condition need no extra parentheses.

Complexity

Time: O(1). At most four comparisons and four min or max calls run, whatever the values are.

Space: O(1). Only the three parameters are used.

Edge cases and common mistakes

Duplicates. With 5, 5, 1 the sorted order is 1, 5, 5, so the second largest by position is 5. The function returns 5 from the first test, since 1 <= 5 <= 5. With 5, 1, 5, a is 5, b.min(c) is 1 and b.max(c) is 5, so a again passes. When all three are equal, the function returns a, which equals the others.
Negative numbers. The comparisons work the same: for -1, -5, 0 the function returns -1.
Using strict comparisons. With < instead of <=, duplicates would fail every test, and the function would fall through to c even when c isn't the middle value. For 5, 5, 1 it would return 1.
Testing the wrong pair. The test for a must look at b and c, not at a itself. Mixing up the names yields a condition that is true for the wrong number.
Confusing the middle with the median of a larger set. This approach works because there are exactly three values. For more values, sorting or a selection method is needed.

Testing

a = 7, b = 3, c = 9 gives 7.
a = 12, b = 8, c = 3 gives 8.
a = 1, b = 2, c = 3 gives 2.
a = 3, b = 2, c = 1 gives 2.
a = 5, b = 5, c = 1 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