414. Third Maximum Number
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 30.7%
Problem Breakdown
The problem requires finding the third maximum number in an integer array nums. If the third maximum does not exist (i.e., there are fewer than three distinct numbers), we should return the maximum number. The input is a list of integers, and the output is a single integer. Key constraints include handling duplicates, negative numbers, and ensuring the solution has linear time complexity.
Intuition
A brute-force approach would involve sorting the array and then selecting the third last element if it exists. However, this approach has a time complexity of O(n log n), which is not optimal for large arrays. The key insight is to maintain three variables to track the top three distinct maximum numbers as we iterate through the array once.
Approach
- Initialize three variables
first,second, andthirdto negative infinity. These will store the first, second, and third maximum numbers respectively. - Iterate through each number in the array:
- If the current number is greater than
first, updatethirdto besecond,secondto befirst, andfirstto be the current number. - Else if the current number is greater than
secondand not equal tofirst, updatethirdto besecond, andsecondto be the current number. - Else if the current number is greater than
thirdand not equal tosecondorfirst, updatethirdto be the current number.
- If the current number is greater than
- After iterating through the array, check if
thirdis still negative infinity. If it is, returnfirst; otherwise, returnthird.
Complexity Analysis
- Time complexity: O(n), where n is the length of the input array. We iterate through the array once.
- Space complexity: O(1), as we use a constant amount of extra space.
Solution
def thirdMax(nums):
first = second = third = float('-inf')
for num in nums:
if num > first:
third = second
second = first
first = num
elif num > second and num != first:
third = second
second = num
elif num > third and num != second and num != first:
third = num
return third if third != float('-inf') else first
Edge Cases Handled
- Empty Array: The function initializes
first,second, andthirdto negative infinity, so it will correctly return the maximum number in an empty array. - Duplicates: The conditionals ensure that duplicates do not affect the ranking of distinct numbers.
- Negative Numbers: The use of negative infinity ensures that negative numbers are handled correctly without special cases.
- Single Element Array: If the array has only one element,
thirdremains negative infinity, and the function returns the single element as the maximum.