Start learning free

LESSON 92 OF 410 · CONDITIONAL STATEMENTS - CHALLENGES

Second Largest Number in O(1) Time and O(1) Space using Python

Practice Read the full explanation

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
    Ctrl + Enter to check

    PYTHON · CONDITIONAL STATEMENTS - CHALLENGES

    Second Largest Value in Python, explained

    Understanding the Problem

    The core challenge of this problem is to identify the second largest number among three given integers. This problem is significant in various applications where ranking or ordering of elements is required. A common pitfall is to overcomplicate the solution, but given the constraints, a simple comparison-based approach is sufficient.

    Approach

    To solve this problem, we need to compare the three integers and determine which one is the second largest. A naive solution might involve sorting the numbers, but this is not optimal given the constraints. Instead, we can use a series of conditional checks to find the second largest number directly.

    Naive Solution

    A naive solution would be to sort the three numbers and return the second element. However, sorting has a time complexity of O(n log n), which is not suitable for this problem.

    Optimized Solution

    We can determine the second largest number by using a few conditional checks. The idea is to check each number and see if it lies between the other two numbers. If it does, it is the second largest number.

    Algorithm

    def second_largest(A, B, C):
    # Check if A is the second largest
    if A >= min(B, C) and A <= max(B, C):
        return A
    # Check if B is the second largest
    if B >= min(A, C) and B <= max(A, C):
        return B
    # If neither A nor B is the second largest, then C must be the second largest
    return C

    Code Implementation

    def second_largest(A, B, C):
    # Check if A is the second largest
    if A >= min(B, C) and A <= max(B, C):
        return A
    # Check if B is the second largest
    if B >= min(A, C) and B <= max(A, C):
        return B
    # If neither A nor B is the second largest, then C must be the second largest
    return C

# Test cases
print(second_largest(7, 3, 9))  # Output: 7
print(second_largest(12, 8, 3))  # Output: 8

    Complexity Analysis

    The time complexity of this solution is O(1) because we are using a constant number of comparisons. The space complexity is also O(1) as we are not using any additional space.

    Edge Cases

    Potential edge cases include:

    • All three numbers are the same (e.g., A = B = C = 5). The function should still return one of the numbers as the second largest.
    • Two numbers are the same and the third is different (e.g., A = B = 5, C = 10). The function should correctly identify the second largest number.

    Testing

    To test the solution comprehensively, consider the following test cases:

    # Test cases
print(second_largest(7, 3, 9))  # Output: 7
print(second_largest(12, 8, 3))  # Output: 8
print(second_largest(5, 5, 5))  # Output: 5
print(second_largest(5, 5, 10))  # Output: 5
print(second_largest(10, 5, 5))  # Output: 5

    Thinking and Problem-Solving Tips

    When approaching such problems, it's essential to break down the problem into smaller parts and think about the simplest way to achieve the solution. Practice solving similar problems and study different algorithms to improve problem-solving skills.

    Conclusion

    In this blog post, we discussed how to find the second largest number among three integers in O(1) time and O(1) space using Python. We explored the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills.

    Additional Resources

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