Leetcode #414: Third Maximum Number
In this guide, we solve Leetcode #414 Third Maximum Number in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Easy
- Premium: No
- Tags: Array, Sorting
Intuition
Sorting reveals structure that is hard to see in the original order.
Once sorted, a linear scan is usually enough to compute the answer.
Approach
Sort the data and sweep through it while maintaining a small state.
This keeps the logic straightforward and reliable.
Steps:
- Sort the data.
- Scan in order while maintaining state.
- Update the best answer.
Example
Input: nums = [3,2,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2.
The third distinct maximum is 1.
Python Solution
class Solution:
def thirdMax(self, nums: List[int]) -> int:
m1 = m2 = m3 = -inf
for num in nums:
if num in [m1, m2, m3]:
continue
if num > m1:
m3, m2, m1 = m2, m1, num
elif num > m2:
m3, m2 = m2, num
elif num > m3:
m3 = num
return m3 if m3 != -inf else m1
Complexity
The time complexity is , where is the length of the array nums. The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.