Third Maximum Number
EasyPrompt
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 - 1
Follow up: Can you find an
O(n) solution?Approaches
3 approaches with complexity analysis and trade-offs.
This is the most optimal approach, solving the problem in a single pass through the array with constant extra space. It involves maintaining three variables to track the top three distinct maximums seen so far.
Algorithm
- Initialize three nullable
Integervariables:max1,max2,max3tonull. - Iterate through each
numin thenumsarray. - If
numis equal to any ofmax1,max2, ormax3, continue to the next iteration to skip duplicates. - If
max1isnullornum > max1, update the maximums:max3 = max2,max2 = max1,max1 = num. - Else if
max2isnullornum > max2, update:max3 = max2,max2 = num. - Else if
max3isnullornum > max3, update:max3 = num. - After the loop, check if
max3isnull. If it is, returnmax1. Otherwise, returnmax3.
Walkthrough
We use three variables, max1, max2, and max3, to store the first, second, and third distinct maximums. To handle the edge case where Integer.MIN_VALUE is one of the maximums, we can use nullable Integer objects, initializing them to null.
We iterate through the input array nums once. For each number, we first check if it's a duplicate of the numbers already stored in max1, max2, or max3. If it is, we skip it. Otherwise, we compare the number with max1, max2, and max3 and update them accordingly:
- If the number is greater than
max1, it becomes the newmax1, and the oldmax1andmax2are shifted down tomax2andmax3. - If the number is not greater than
max1but is greater thanmax2, it becomes the newmax2, and the oldmax2is shifted tomax3. - If the number is not greater than
max1ormax2but is greater thanmax3, it becomes the newmax3. After the loop, ifmax3is stillnull, it means we found fewer than three distinct numbers, so we returnmax1(the overall maximum). Otherwise, we returnmax3.
class Solution { public int thirdMax(int[] nums) { Integer max1 = null; Integer max2 = null; Integer max3 = null; for (Integer num : nums) { // Skip duplicates if (num.equals(max1) || num.equals(max2) || num.equals(max3)) { continue; } if (max1 == null || num > max1) { max3 = max2; max2 = max1; max1 = num; } else if (max2 == null || num > max2) { max3 = max2; max2 = num; } else if (max3 == null || num > max3) { max3 = num; } } // If max3 is null, it means there are fewer than 3 distinct numbers. // In this case, return the overall maximum, which is max1. return max3 == null ? max1 : max3; }}Complexity
Time
O(N), as we iterate through the array only once.
Space
O(1), as we only use a fixed number of extra variables regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Does not modify the input array.
Cons
The logic can be slightly more complex to write correctly due to handling nulls and multiple conditions.
This approach involves sorting the array first. Once sorted, the distinct maximums can be found by iterating from the end of the array.
Algorithm
- Sort the input array
numsin non-decreasing order. - Iterate through the sorted array from right to left to find distinct elements.
- Use a counter
distinctCountto track the number of distinct maximums found. - The first element from the end is the first maximum. Increment
distinctCount. - Continue iterating backwards. If the current element is smaller than the previous one (from the right), it's a new distinct maximum. Increment
distinctCount. - If
distinctCountreaches 3, the current element is the third maximum. Return it. - If the loop completes and
distinctCountis less than 3, it means a third maximum does not exist. In this case, return the largest element in the array (the last element of the sorted array).
Walkthrough
The core idea is that after sorting the array in ascending order, the largest elements will be at the end. We can then iterate from the end of the sorted array, keeping track of the distinct numbers we encounter. The first distinct number from the end is the maximum, the second is the second maximum, and the third is the third maximum. If we traverse the entire array and find fewer than three distinct numbers, we return the overall maximum.
import java.util.Arrays; class Solution { public int thirdMax(int[] nums) { Arrays.sort(nums); int n = nums.length; // The maximum element is always at the end after sorting int max = nums[n - 1]; int distinctCount = 1; // Iterate from the second to last element for (int i = n - 2; i >= 0; i--) { // If we find a new smaller element, it's a new distinct maximum if (nums[i] < nums[i + 1]) { distinctCount++; } // If we have found 3 distinct maximums, the current element is the third one if (distinctCount == 3) { return nums[i]; } } // If we finish the loop and haven't found 3 distinct maximums, // it means the third maximum doesn't exist. Return the overall maximum. return max; }}Complexity
Time
O(N log N), where N is the number of elements in the array. The dominant operation is sorting the array.
Space
O(log N) or O(N) depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitives uses a variant of Quicksort which has an average space complexity of O(log N) for the recursion stack.
Trade-offs
Pros
Simple to understand and implement.
Leverages standard library functions.
Cons
Not the most efficient in terms of time complexity due to the sorting step.
Modifies the input array, which might not be desirable in some contexts.
This approach uses a Set data structure to efficiently store only the unique elements from the input array. After populating the set, we can easily find the third maximum.
Algorithm
- Create a
HashSetto store unique elements. - Iterate through the
numsarray and add each number to the set. - Check the size of the set. If it's less than 3, find the maximum element in the set and return it.
- If the set size is 3 or more, find and remove the maximum element.
- Find and remove the new maximum element.
- The largest remaining element in the set is the third maximum. Return it.
Walkthrough
First, we iterate through the input array nums and add each element to a HashSet. The HashSet automatically handles duplicates, so after the iteration, it will contain all the unique numbers from the array.
Then, we check the size of the set. If the size is less than 3, it's impossible to have a third maximum, so we find and return the maximum element in the set.
If the size is 3 or more, we can find the third maximum by repeatedly finding and removing the largest element from the set. We remove the largest element, then remove the new largest element. The largest element remaining in the set will be the third distinct maximum.
import java.util.HashSet;import java.util.Set;import java.util.Collections; class Solution { public int thirdMax(int[] nums) { Set<Integer> distinctNums = new HashSet<>(); for (int num : nums) { distinctNums.add(num); } // If there are fewer than 3 distinct numbers, return the maximum. if (distinctNums.size() < 3) { return Collections.max(distinctNums); } // Remove the first maximum distinctNums.remove(Collections.max(distinctNums)); // Remove the second maximum distinctNums.remove(Collections.max(distinctNums)); // The remaining maximum is the third maximum return Collections.max(distinctNums); }}Complexity
Time
O(N). Populating the set takes O(N) time. Finding and removing the maximums from the set takes time proportional to the number of unique elements (K), which is at most N. So, the total time is O(N).
Space
O(K), where K is the number of distinct elements in the array. In the worst case, all elements are distinct, so the space complexity is O(N).
Trade-offs
Pros
More efficient than the sorting approach in terms of time complexity.
Conceptually straightforward.
Cons
Requires extra space to store the unique elements, which can be up to O(N).
Solutions
Solution
class Solution {public int thirdMax(int[] nums) { long m1 = Long.MIN_VALUE; long m2 = Long.MIN_VALUE; long m3 = Long.MIN_VALUE; for (int num : nums) { if (num == m1 || num == m2 || num == m3) { continue; } if (num > m1) { m3 = m2; m2 = m1; m1 = num; } else if (num > m2) { m3 = m2; m2 = num; } else if (num > m3) { m3 = num; } } return (int)(m3 != Long.MIN_VALUE ? m3 : m1); }}class Solution {public: int thirdMax(vector<int> &nums) { long m1 = LONG_MIN, m2 = LONG_MIN, m3 = LONG_MIN; for (int num : nums) { if (num == m1 || num == m2 || num == m3) continue; if (num > m1) { m3 = m2; m2 = m1; m1 = num; } else if (num > m2) { m3 = m2; m2 = num; } else if (num > m3) { m3 = num; } } return (int)(m3 != LONG_MIN ? m3 : m1); }};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 m1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.