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.
Example 1:
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.
Example 2:
Input: nums = [1,2] Output: 2 Explanation: The first distinct maximum is 2. The second distinct maximum is 1. The third distinct maximum does not exist, so the maximum (2) is returned instead.
Example 3:
Input: nums = [2,2,3,1] Output: 1 Explanation: The first distinct maximum is 3. The second distinct maximum is 2 (both 2's are counted together since they have the same value). The third distinct maximum is 1.
Constraints:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1Follow up: Can you find an
O(n) solution?Problem Overview: Given an integer array, return the third distinct maximum value. If the array has fewer than three distinct values, return the maximum element instead. Duplicate values should be ignored when counting distinct maximums.
Approach 1: Sorting and Distinct Selection (O(n log n) time, O(1) or O(n) space)
Sort the array in descending order and scan for distinct values. After sorting, iterate through the array and count unique numbers until the third distinct value appears. If you reach the end before finding three unique numbers, return the first element (the maximum). The key idea is that sorting groups duplicates together, making it easy to skip them while scanning. This approach is simple and readable but costs O(n log n) time due to the sorting step.
This method works well when simplicity matters more than optimal performance. It relies heavily on sorting behavior and sequential scanning of the array.
Approach 2: Iterative Approach without Extra Space (O(n) time, O(1) space)
Track the top three distinct maximum values while scanning the array once. Maintain three variables: first, second, and third. For each number, skip it if it matches any of these values to enforce distinctness. Otherwise update the three variables by shifting values down whenever a larger number appears.
The core insight: you don't need to sort the entire array to know the three largest distinct numbers. A single pass with careful comparisons maintains the correct ordering. Each element is processed once, giving O(n) time complexity and constant O(1) space.
This approach is optimal for interview scenarios. It demonstrates control over comparisons, handling duplicates, and maintaining ordered state without auxiliary data structures.
Recommended for interviews: The single-pass iterative approach is what most interviewers expect. The sorting solution shows baseline understanding, but the O(n) scan with three variables demonstrates stronger algorithmic thinking and careful handling of edge cases like duplicates and negative numbers.
This approach involves first sorting the array and then selecting distinct maximums from the sorted array. We can use a set to easily manage distinct elements. After constructing a set, we check if the size of the set is at least 3; if so, we find the third largest by accessing the sorted array of distinct elements, otherwise, return the maximum element.
This C solution uses the C standard library function qsort to sort the array in descending order. We then traverse the sorted array to count distinct elements. We track the number of distinct numbers found and when the count reaches three, we return the number. If we pass through the entire array without finding three distinct maximums, we return the first number.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) as sorting is done in place with qsort.
This approach keeps track of the three largest distinct numbers iteratively as it processes the array. It uses variables to track them and updates them as it iterates through each number. This way, it can achieve O(n) time complexity without additional set or sorting overhead.
This C solution uses additional variables (initialized to the smallest possible value using LONG_MIN) to track the first, second, and third maximum numbers. During the iteration, if the current number doesn't match the tracked maximums, it updates the respective maximum. At the end of the loop, it checks if the third max was updated from its initialized state, returning it only if so; otherwise, it returns the first maximum.
Time Complexity: O(n) because it performs a single pass over the array.
Space Complexity: O(1) as only constant space is used for tracking the maximums.
We can use three variables m_1, m_2, and m_3 to represent the first, second, and third largest numbers in the array respectively. Initially, we set these three variables to negative infinity.
Then, we iterate through each number in the array. For each number:
m_1, m_2, or m_3, we skip this number.m_1, we update the values of m_1, m_2, and m_3 to m_2, m_3, and this number respectively.m_2, we update the values of m_2 and m_3 to m_3 and this number respectively.m_3, we update the value of m_3 to this number.Finally, if the value of m_3 has not been updated, it means that there is no third largest number in the array, so we return m_1. Otherwise, we return m_3.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Sorting and Distinct Selection Approach | Time Complexity: O(n log n) due to the sorting operation. |
| Iterative Approach without Extra Space | Time Complexity: O(n) because it performs a single pass over the array. |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Distinct Selection | O(n log n) | O(1) or O(n) | When readability and quick implementation matter more than optimal runtime |
| Iterative Three-Max Tracking | O(n) | O(1) | Best general solution; preferred in interviews and large datasets |
LeetCode 414. Third Maximum Number Solution Explained - Java • Nick White • 25,982 views views
Watch 9 more video solutions →Practice Third Maximum Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor