Start learning free

LESSON 87 OF 338 · CONDITIONAL STATEMENTS - CHALLENGES

Second Largest Value in Go: O(1) with min and max

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

    GO · CONDITIONAL STATEMENTS - CHALLENGES

    Second Largest Value in Go, explained

    Problem overview

    The function secondLargest receives three integers, a, b and c, and returns the one that is neither the largest nor the smallest. For 7, 3, 9 the answer is 7. For 12, 8, 3 it is 8.

    The algorithm must run in O(1) time and use O(1) extra space. With only three numbers, sorting is not needed; a few comparisons are enough.

    Approach: test each candidate

    The answer is one of three numbers, so test them one at a time. A number x is the second largest when it sits between the other two: not below the smaller of them and not above the larger of them. For a that is min(b, c) <= a && a <= max(b, c).

    Check a first. If it does not qualify, check b the same way. If neither does, c must be the middle value, so return it without a test. This leaves three returns and two conditions.

    The comparisons use <= on both sides, so equal values are allowed. With 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 function returns 5, and 5 is correct: the sorted list is 2, 5, 5.

    Step by step

    1. Test a. Compute min(b, c) and max(b, c). If a lies between them, inclusive, return a.
    2. Test b. Do the same with min(a, c) and max(a, c), and return b if it lies between them.
    3. Return c. If a and b are not in the middle, the only remaining candidate is c, so no condition is required.

    The solution in Go

    func secondLargest(a, b, 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
}

    Tracing 7, 3, 9: min(3, 9) is 3 and max(3, 9) is 9, and 3 <= 7 && 7 <= 9 is true, so it returns 7. Tracing 12, 8, 3: for a, the range is 3 to 8 and 12 is outside; for b, the range is 3 to 12 and 8 is inside, so it returns 8.

    Some Go details:

    • Built-in min and max. Since Go 1.21 these are part of the language, so no import is needed. They accept two or more arguments of the same ordered type, and they work on int, float64 and strings. In earlier Go versions you had to write them yourself. This lesson targets Go 1.22.
    • Grouped parameters. a, b, c int gives all three parameters the type int.
    • Precedence. Comparisons bind tighter than &&, so each condition reads as two comparisons joined by "and", with no extra parentheses.
    • Final return. The function ends with return c instead of a third if. Go demands a return at the end of a function with a result, and the logic makes the last test unnecessary.

    Complexity

    The function evaluates a fixed number of comparisons and calls to min and max on at most three numbers, so time is O(1). It creates no data structures, so extra space is O(1).

    Edge cases and common mistakes

    • Duplicates. With 5, 5, 2 the answer is 5, and with 5, 5, 5 it is 5. The lesson counts the middle position in sorted order, not the second distinct value.
    • Negative numbers. secondLargest(-1, -5, -3) returns -3. Nothing in the logic depends on sign.
    • Strict comparisons. Using < instead of <= would reject a when it equals the smaller or larger of the others. For 5, 5, 2 neither a nor b would pass, and the function would fall through to return c and answer 2.
    • Swapping the roles. For b, the others are a and c. Writing min(b, c) in the second test by copy-paste checks the wrong pair.
    • Testing only one side. A check such as a < max(b, c) accepts the smallest number too. Both bounds are needed.

    Testing

    • secondLargest(7, 3, 9) gives 7.
    • secondLargest(12, 8, 3) gives 8.
    • secondLargest(1, 2, 3) gives 2.
    • secondLargest(3, 2, 1) gives 2.
    • secondLargest(5, 5, 2) gives 5.
    • secondLargest(-1, -5, -3) gives -3.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free