Third Maximum Number

EASY

Description

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 <= 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1

Follow up: Can you find an O(n) solution?

Approaches

Checkout 3 different approaches to solve Third Maximum Number. Click on different approaches to view the approach and algorithm in detail.

Single Pass with Constant Space

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.

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 Analysis

Time Complexity: O(N), as we iterate through the array only once.Space Complexity: O(1), as we only use a fixed number of extra variables regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Third Maximum Number. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Third Maximum Number

Algorithms:

Sorting

Data Structures:

Array