Scale Engineer

Third Maximum Number

Easy
#0401Time: 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.
Algorithms
Sorting
Data structures
Array

Prompt

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 Integer variables: max1, max2, max3 to null.
  • Iterate through each num in the nums array.
  • If num is equal to any of max1, max2, or max3, continue to the next iteration to skip duplicates.
  • If max1 is null or num > max1, update the maximums: max3 = max2, max2 = max1, max1 = num.
  • Else if max2 is null or num > max2, update: max3 = max2, max2 = num.
  • Else if max3 is null or num > max3, update: max3 = num.
  • After the loop, check if max3 is null. If it is, return max1. Otherwise, return max3.

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 new max1, and the old max1 and max2 are shifted down to max2 and max3.
  • If the number is not greater than max1 but is greater than max2, it becomes the new max2, and the old max2 is shifted to max3.
  • If the number is not greater than max1 or max2 but is greater than max3, it becomes the new max3. After the loop, if max3 is still null, it means we found fewer than three distinct numbers, so we return max1 (the overall maximum). Otherwise, we return max3.
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.

Solutions

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);  }}

Video 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.

← Previous

Previous problem

Next →

Next problem