LESSON 89 OF 414 · CONDITIONAL STATEMENTS - CHALLENGES

Second Largest Value in Scala: Three Integers with if and math.min

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 Scala, explained

Problem overview

The method secondLargest of class Solution receives three integers, A, B and C, and returns the one in the middle: the second largest. In the first example, A = 7, B = 3, C = 9. The largest is 9, the smallest is 3, so the answer is 7. In the second, A = 12, B = 8, C = 3 gives 8.

The note asks for O(1) time and O(1) extra space. With a fixed number of inputs, that means a few comparisons and no collections.

Approach: test each candidate

The answer is always one of the three inputs, so check them one at a time. A number is the second largest when it sits between the other two: it is at least as big as the smaller of them and at most as big as the larger. For A that reads math.min(B, C) <= A && A <= math.max(B, C).

Sorting the three numbers and picking the middle one would also work, but it builds a collection for no good reason. Three comparisons are simpler and need no extra memory.

You only need to test two candidates. If neither A nor B is in the middle, the middle one must be C, so the last case needs no condition.

Step by step

Test A. Compute the smaller and the larger of B and C with math.min and math.max. If A lies between them, return it.
Test B. Do the same with A and C as the other two numbers. If B lies between them, return it.
Return C. The first two tests failed, so C is the middle value.

The solution in Scala

class Solution {
    def secondLargest(A: Int, B: Int, C: Int): Int = {
        if (math.min(B, C) <= A && A <= math.max(B, C)) {
            return A
        }
        if (math.min(A, C) <= B && B <= math.max(A, C)) {
            return B
        }
        return C
    }
}

The Scala details worth knowing:

math.min and math.max. They live in the scala.math package, which is available as math without an import. They work on Int values and return an Int.
Explicit return. In Scala the last expression of a block is its value, so many programs leave out return. This solution uses it to leave early, which is legal in a method with a declared result type (: Int). The same method could be written as an if / else if / else chain whose branches are just A, B and C.
&&. Both comparisons must hold. It stops at the first one that is false.
Int parameters. Parameters are vals: you can read them but not reassign them.

Complexity

Time: O(1). The method makes at most four min / max calls and four comparisons, whatever the values are.

Space: O(1). It creates no arrays or lists, only the values it returns.

Edge cases and common mistakes

Ties. Duplicates are why the comparisons use <= and not <. With (5, 5, 5) the method returns 5. With (4, 9, 9) it returns 9: the second largest is counted by position, so a repeated maximum is its own second largest. With (9, 9, 4) it also returns 9.
Strict comparisons. With < in place of <=, a tie makes both tests fail, and the method wrongly falls through to C. For (9, 9, 4) it would return 4 instead of 9.
Mixing up the pairs. The test for A uses B and C, the test for B uses A and C. Putting the candidate inside its own min or max makes the test always true.
Returning the middle by order. The answer depends on the values, not on which argument is in the middle position. For (1, 2, 3), (3, 2, 1) and (2, 3, 1) the result is 2 every time.

Testing

(7, 3, 9) gives 7.
(12, 8, 3) gives 8.
(1, 2, 3) gives 2.
(3, 2, 1) gives 2.
(5, 5, 5) gives 5.
(9, 9, 4) gives 9.

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

Start learning free