Start learning free

LESSON 88 OF 348 · CONDITIONAL STATEMENTS - CHALLENGES

Second Largest Value in Kotlin: O(1) with minOf and maxOf

Practice Read the full explanation

Given 3 integers, 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 min(B, C) <= A and A <= max(B, C). We can write an if statement checking these conditions and if they hold, return A: 
if A >= min(B, C) and A <= max(B, C):
	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 min(A, C) <= B and B <= max(A, C). We can write an if statement checking these conditions and if they hold, return B. 
if A >= min(B, C) and A <= max(B, C):
	return A
if B >= min(A, C) and B <= max(A, C):
	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: 
if A >= min(B, C) and A <= max(B, C):
	return A
if B >= min(A, C) and B <= max(A, C):
	return B
return C

STEP 1 OF 3
    Ctrl + Enter to check

    KOTLIN · CONDITIONAL STATEMENTS - CHALLENGES

    Second Largest Value in Kotlin, explained

    Problem overview

    The function secondLargest in class Solution receives three integers, A, B and C, and returns the one that is neither the largest nor the smallest, which is the middle value.

    For A = 7, B = 3, C = 9 the sorted order is 3, 7, 9, so the answer is 7. For A = 12, B = 8, C = 3 the sorted order is 3, 8, 12, so the answer is 8.

    The statement asks for O(1) time and O(1) extra space. With only three numbers, that is natural: the function does a fixed number of comparisons and stores nothing.

    Approach: test each candidate

    There are only three candidates. One of them must be the middle value, so the plan is to test A, then B, and to return C if neither fits.

    A number is the middle value when it sits between the other two, inclusive. 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. Sorting the three numbers would also work, but a sort is more machinery than three numbers need, and the conditions above show the idea directly.

    Using "less than or equal" instead of "less than" matters when values repeat. With A = 5, B = 5, C = 9, the sorted order is 5, 5, 9, and the middle value is 5. Both conditions hold for A because min(B, C) is 5, which equals A.

    Step by step

    1. Check A. Build one condition from two comparisons joined with &&: the smaller of B and C is at most A, and A is at most the larger of the two. If both hold, return A at once.
    2. Check B. It is the same test with the roles changed: compare B against the smaller and larger of A and C.
    3. Return C. If neither A nor B is the middle value, then C must be. No third check is needed, and writing one would only add code that can never change the result.

    The solution in Kotlin

    class Solution {
    fun secondLargest(A: Int, B: Int, C: Int): Int {
        if (minOf(B, C) <= A && A <= maxOf(B, C)) {
            return A
        }
        if (minOf(A, C) <= B && B <= maxOf(A, C)) {
            return B
        }
        return C
    }
}

    Kotlin details worth knowing:

    • minOf and maxOf are functions, not methods. They are part of the standard library, so you call them as minOf(B, C) with no import. They also accept three arguments, as in maxOf(A, B, C).
    • && short-circuits. If the left comparison is false, Kotlin doesn't evaluate the right one. Here both sides are cheap, so it only affects readability.
    • The parameter names start with capitals. Kotlin convention prefers a, b and c, but the lesson's tests call the function by position, and the names A, B, C are what the editor gives you, so keep them.
    • The function body must return on every path. A function declared with return type Int that can reach the closing brace without returning doesn't compile. The final return C guarantees that this one always returns.
    • Int comparisons don't overflow. The solution only compares values and never adds or subtracts them, so even Int.MAX_VALUE and Int.MIN_VALUE are safe inputs.

    Complexity

    Time: O(1). The function runs at most four minOf/maxOf calls and four comparisons, whatever the values are.

    Space: O(1). It creates no arrays, lists or other structures that grow with the input.

    Edge cases and common mistakes

    • Equal values. secondLargest(4, 4, 4) returns 4, and secondLargest(9, 5, 5) returns 5. Using strict < in the conditions would skip the right candidate when two values tie.
    • Negative numbers. The comparisons work the same way: secondLargest(-1, -5, -3) returns -3.
    • Swapping minOf and maxOf. If the smaller bound is written as maxOf, the condition can almost never hold, and the function falls through to return C for the wrong inputs.
    • Returning the position instead of the value. The function returns the number itself, not "A" or its place in the sorted order.
    • Checking only the top. Testing whether A is greater than one of the others is not enough. The middle value must be at least one number and at most another.

    Testing

    • secondLargest(7, 3, 9) gives 7.
    • secondLargest(12, 8, 3) gives 8.
    • secondLargest(1, 2, 3) gives 2, returned by the second check.
    • secondLargest(3, 1, 2) gives 2, the case where C is the answer.
    • secondLargest(5, 5, 9) gives 5.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free