Taro Logo

Third Maximum Number

Easy
Amazon logo
Amazon
1 view
Topics:
Arrays

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number. Your solution must be O(n).

For example:

  1. nums = [3,2,1] should return 1 because the first distinct maximum is 3, the second is 2, and the third is 1.
  2. nums = [1,2] should return 2 because the first distinct maximum is 2, the second is 1, and the third does not exist, thus return the max which is 2.
  3. nums = [2,2,3,1] should return 1 because the first distinct maximum is 3, the second distinct maximum is 2 (both 2's are counted together since they have the same value), and the third distinct maximum is 1.

What is the most efficient way to solve this and what is the Big O runtime?

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What should I return if the array has fewer than three distinct numbers?
  2. Can the input array contain duplicate numbers, and if so, should the third maximum be based on distinct values or the literal third largest value including duplicates?
  3. Can the input array be empty or null?
  4. What is the range of values for the numbers in the input array?
  5. Is the third maximum defined as the third largest distinct value, or simply the third largest number when considering duplicates?

Brute Force Solution

Approach

The brute force approach to finding the third largest number involves checking all the numbers to determine the largest, then the second largest, and finally the third largest. We essentially compare each number against all others to find these three distinct values. It is like manually sorting through a list to find specific ranks.

Here's how the algorithm would work step-by-step:

  1. First, find the absolute largest number in the group of numbers.
  2. Next, find the largest number that is smaller than the absolute largest number you previously found. This will be the second largest number.
  3. Then, find the largest number that is smaller than the second largest number you found. This will be your third largest number.
  4. If you can't find a distinct third largest number because there aren't enough different values, just return the absolute largest number you found initially.

Code Implementation

def third_max(numbers):
    absolute_largest_number = float('-inf')
    second_largest_number = float('-inf')
    third_largest_number = float('-inf')

    for number in numbers:
        if number > absolute_largest_number:
            # New largest, shift others down

            third_largest_number = second_largest_number

            second_largest_number = absolute_largest_number

            absolute_largest_number = number

        elif number > second_largest_number and number < absolute_largest_number:
            # New second largest, shift third down

            third_largest_number = second_largest_number

            second_largest_number = number

        elif number > third_largest_number and number < second_largest_number:
            # New third largest number

            third_largest_number = number

    # If no distinct third max, return largest
    if third_largest_number == float('-inf'):
        return absolute_largest_number

    return third_largest_number

Big(O) Analysis

Time Complexity
O(n²)The algorithm finds the largest, second largest, and third largest numbers sequentially. Finding the largest number requires iterating through all n elements. Then, finding the second largest requires another iteration through n elements (or fewer if optimized), and similarly for the third largest. Therefore, we iterate through the array a maximum of three times, each potentially requiring n comparisons leading to approximately 3 * n * n operations in total. After simplification, the time complexity is O(n²).
Space Complexity
O(1)The provided solution involves finding the largest, second largest, and third largest numbers by iteratively comparing numbers. It only requires storing a fixed number of variables to hold the largest, second largest, and third largest values encountered so far. The number of variables needed does not scale with the input size N, which is the number of elements in the input array. Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Optimal Solution

Approach

The goal is to find the third largest number in a collection. Instead of sorting everything or checking every possibility, we'll keep track of the three largest numbers we've seen so far and update them as needed. This avoids unnecessary work and gives us the answer directly.

Here's how the algorithm would work step-by-step:

  1. Start by creating three slots to hold the three largest numbers we find. Initially, these slots are empty.
  2. Go through each number in the collection one by one.
  3. For each number, compare it to the numbers in our three slots. If the number is larger than the smallest of the three largest numbers we've stored, we update the slots accordingly, bumping the smaller numbers down.
  4. Be careful to handle cases where a number might be a duplicate of one we've already seen. In such case, don't update the slots.
  5. After examining all numbers in the collection, check if we successfully found three distinct largest numbers. If we did, the smallest of the three numbers we are storing is the answer. Otherwise, if we found less than three unique numbers, then the largest number will be the answer.

Code Implementation

def third_max(numbers):    first_maximum = float('-inf')
    second_maximum = float('-inf')
    third_maximum = float('-inf')

    for number in numbers:
        if number in (first_maximum, second_maximum, third_maximum):
            continue

        if number > first_maximum:
            # Update the top three maximums
            third_maximum = second_maximum
            second_maximum = first_maximum
            first_maximum = number

        elif number > second_maximum:
            # Update the second and third maximums
            third_maximum = second_maximum
            second_maximum = number

        elif number > third_maximum:
            # Update the third maximum
            third_maximum = number

    # Check if there are at least three distinct numbers.
    if third_maximum == float('-inf'):
        return first_maximum
    else:
        return third_maximum

Big(O) Analysis

Time Complexity
O(n)We iterate through the input array of size n once. For each element, we perform a constant number of comparisons and potentially updates to our three largest numbers. The number of comparisons and updates does not depend on the size of the input. Therefore, the time complexity is directly proportional to the number of elements in the array, resulting in O(n).
Space Complexity
O(1)The provided solution maintains three variables to store the largest, second largest, and third largest numbers encountered so far. The number of these variables is fixed and does not depend on the size of the input array, which we denote as N. Therefore, the algorithm's space usage remains constant regardless of the input size. Consequently, the space complexity is O(1).

Edge Cases

CaseHow to Handle
Empty or null input arrayReturn null or throw an IllegalArgumentException as the third maximum does not exist for an empty array.
Array with less than 3 distinct elementsReturn the maximum element in the array according to the problem description.
Array containing only two distinct elementsReturn the largest element in the array according to the problem description.
Array with all identical elementsReturn the identical element since that will be the maximum (and technically the third maximum if the definition is followed).
Array containing negative numbers onlyThe solution should correctly identify the third largest (least negative) number among the negative numbers.
Array containing duplicate numbers with only two distinct valuesThe solution needs to return the largest value, satisfying problem requirements.
Integer overflow when comparing very large numbers (potential with min/max)Use long data type to store intermediate results and comparisons to avoid potential overflow issues.
Large input array affecting algorithm performance (time complexity)Consider using a min-heap of size 3 to efficiently track the 3 largest numbers for O(n) time complexity.