{x}
blog image

Third Maximum Number

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?

Solution Explanation for Finding the Third Maximum Number

This problem asks to find the third distinct maximum number in an integer array. If the third maximum doesn't exist, return the maximum number.

Approach: Single Pass

The most efficient approach is a single-pass algorithm using a constant amount of extra space. We maintain three variables to track the largest three distinct numbers encountered so far: m1, m2, and m3.

  1. Initialization: Initialize m1, m2, and m3 to the smallest possible integer value (-∞ or Long.MIN_VALUE depending on the language). This ensures that any number in the input array will be larger than the initial values.

  2. Iteration: Iterate through the input array nums. For each number num:

    • Duplicate Check: If num is equal to any of m1, m2, or m3, skip it (we only want distinct numbers).
    • Update Logic: If num is greater than m1 (the current largest), we shift m1 to m2, m2 to m3, and assign num to m1. Otherwise, if num is greater than m2 (the second largest), we shift m2 to m3 and assign num to m2. Finally, if num is greater than m3 (the third largest), we assign num to m3.

  3. Result: After iterating through the entire array, if m3 is still its initial value (meaning no third distinct maximum was found), return m1 (the maximum number). Otherwise, return m3 (the third distinct maximum number).

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array only once.
  • Space Complexity: O(1). We use a constant number of variables (m1, m2, m3) regardless of the input array size.

Code Implementation in Different Languages

Python:

import sys
 
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        m1 = m2 = m3 = -sys.maxsize -1 #Using -sys.maxsize -1 for negative infinity in Python.
        for num in nums:
            if num in [m1, m2, m3]:
                continue
            if num > m1:
                m3 = m2
                m2 = m1
                m1 = num
            elif num > m2:
                m3 = m2
                m2 = num
            elif num > m3:
                m3 = num
        return m3 if m3 != -sys.maxsize -1 else m1

Java:

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

C++:

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long long m1 = LLONG_MIN, m2 = LLONG_MIN, m3 = LLONG_MIN;
        for (long long 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 (m3 == LLONG_MIN) ? m1 : m3;
    }
};

Go:

func thirdMax(nums []int) int {
	m1, m2, m3 := math.MinInt64, math.MinInt64, math.MinInt64
	for _, num := range nums {
		if num == m1 || num == m2 || num == m3 {
			continue
		}
		if num > m1 {
			m3, m2, m1 = m2, m1, num
		} else if num > m2 {
			m3, m2 = m2, num
		} else if num > m3 {
			m3 = num
		}
	}
	if m3 == math.MinInt64 {
		return m1
	}
	return m3
}

These code snippets all implement the same single-pass algorithm, differing only in syntax and specific language features for representing the smallest possible integer value. They all achieve O(n) time complexity and O(1) space complexity.