LESSON 89 OF 415 · CONDITIONAL STATEMENTS - CHALLENGES

Second Largest Value in Swift: 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 Swift, explained

Problem overview

The method secondLargest(_ A: Int, _ B: Int, _ C: Int) -> Int in the class Solution receives three integers and returns the one that is second largest. For 7, 3, 9 the answer is 7, because 9 is the largest and 3 the smallest. For 12, 8, 3 the answer is 8. The method must take constant time and constant extra space.

Approach: test each candidate

You could sort the three numbers and pick the middle one, but sorting needs an array and is more work than three numbers deserve. A direct approach is to ask of each number whether it is the middle one.

A number is the second largest when it lies between the other two, ends included. For A, that means the smaller of B and C is at most A, and A is at most the larger of B and C. In symbols: min(B, C) <= A && A <= max(B, C). The same question for B uses A and C.

If neither A nor B is in the middle, C must be. No third test is needed.

Step by step

Test A. If min(B, C) <= A and A <= max(B, C), return A. Swift's global min and max functions take two values of the same type.
Test B. The same check against A and C: if min(A, C) <= B and B <= max(A, C), return B.
Return C. Reaching this line means A and B were not in the middle, so C is.

The solution in Swift

class Solution {
    func secondLargest(_ A: Int, _ B: Int, _ C: Int) -> Int {
        if min(B, C) <= A && A <= max(B, C) {
            return A
        }
        if min(A, C) <= B && B <= max(A, C) {
            return B
        }
        return C
    }
}

Details worth knowing:

Global functions. min and max are called without a receiver, as in min(B, C). They work for any type that can be compared, including Int.
Chained comparisons. Swift has no x <= A <= y form, which is why the check is written as two comparisons joined with &&.
Parentheses. Comparisons bind tighter than &&, so none are needed around each one.
Capitalised parameters. A, B and C are ordinary parameter names. Swift style usually prefers lowercase, but the lesson's method uses these names, so the article does too.

Tracing an example

Take secondLargest(12, 8, 3). For A = 12, min(8, 3) is 3, which is at most 12, but 12 is not at most max(8, 3), which is 8. The first test fails. For B = 8, min(12, 3) is 3, which is at most 8, and 8 is at most max(12, 3), which is 12. The second test passes, so the method returns 8. For secondLargest(7, 3, 9), the first test passes immediately, since 3 is at most 7 and 7 is at most 9.

Complexity

Time: O(1). The method makes at most a fixed number of comparisons and calls to min and max. Space: O(1). It uses no extra storage.

Edge cases and common mistakes

Ties. The comparisons are inclusive. For 5, 5, 2, the first test passes because min(5, 2) is 2, which is at most 5, and 5 is at most max(5, 2), which is 5. The method returns 5. With 4, 4, 4 it returns 4.
Strict comparisons. Using < instead of <= would reject any middle value equal to a neighbour, and the method would return C wrongly.
Mixing up which pair to compare. The check for B must use A and C, not B itself.

Testing

let s = Solution()
print(s.secondLargest(7, 3, 9))
print(s.secondLargest(12, 8, 3))
print(s.secondLargest(5, 5, 2))
print(s.secondLargest(4, 4, 4))
print(s.secondLargest(1, 2, 3))

The output is:

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

Start learning free