Watch 10 video solutions for Third Maximum Number, a easy level problem involving Array, Sorting. This walkthrough by NeetCode has 331,598 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |