Algocademy Logo

Course Outline

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


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.


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