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:
nums = [3,2,1]
should return 1
because the first distinct maximum is 3, the second is 2, and the third is 1.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.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?
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:
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:
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
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:
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
Case | How to Handle |
---|---|
Empty or null input array | Return null or throw an IllegalArgumentException as the third maximum does not exist for an empty array. |
Array with less than 3 distinct elements | Return the maximum element in the array according to the problem description. |
Array containing only two distinct elements | Return the largest element in the array according to the problem description. |
Array with all identical elements | Return the identical element since that will be the maximum (and technically the third maximum if the definition is followed). |
Array containing negative numbers only | The solution should correctly identify the third largest (least negative) number among the negative numbers. |
Array containing duplicate numbers with only two distinct values | The 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. |