Third Maximum Number Problem

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8


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:

1
2
3
4
5
6
7
8


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:

1
2
3
4
5
6
7
8


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.

Solution

Method 1 – Linear Pass

Intuition

To find the third distinct maximum, we can keep track of the top three unique values as we scan the array. By updating these values only when we see a new, larger, or unique number, we ensure we always know the first, second, and third maximums. If there are fewer than three distinct numbers, we return the largest.

Approach

Initialize Three Variables:
- Use three variables to store the first, second, and third maximums, initially set to null or a sentinel value.
Iterate Through the Array:
- For each number, skip it if it matches any of the current maximums (to ensure distinctness).
- If it’s larger than the current first maximum, update all three maximums accordingly.
- Else if it’s larger than the second, update the second and third.
- Else if it’s larger than the third, update the third.
Return the Result:
- If the third maximum is not set, return the first maximum; otherwise, return the third.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
	int thirdMax(vector<int>& nums) {
		long max1 = LONG_MIN, max2 = LONG_MIN, max3 = LONG_MIN;
		for (int n : nums) {
			if (n == max1 || n == max2 || n == max3) continue;
			if (n > max1) {
				max3 = max2; max2 = max1; max1 = n;
			} else if (n > max2) {
				max3 = max2; max2 = n;
			} else if (n > max3) {
				max3 = n;
			}
		}
		return max3 == LONG_MIN ? max1 : max3;
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func thirdMax(nums []int) int {
	max1, max2, max3 := math.MinInt64, math.MinInt64, math.MinInt64
	for _, n := range nums {
		if n == max1 || n == max2 || n == max3 { continue }
		if n > max1 {
			max3, max2, max1 = max2, max1, n
		} else if n > max2 {
			max3, max2 = max2, n
		} else if n > max3 {
			max3 = n
		}
	}
	if max3 == math.MinInt64 { return max1 }
	return max3
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
	public int thirdMax(int[] nums) {
		Long max1 = null, max2 = null, max3 = null;
		for (int n : nums) {
			if (Objects.equals(max1, (long)n) || Objects.equals(max2, (long)n) || Objects.equals(max3, (long)n)) continue;
			if (max1 == null || n > max1) {
				max3 = max2; max2 = max1; max1 = (long)n;
			} else if (max2 == null || n > max2) {
				max3 = max2; max2 = (long)n;
			} else if (max3 == null || n > max3) {
				max3 = (long)n;
			}
		}
		return max3 == null ? max1.intValue() : max3.intValue();
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
	fun thirdMax(nums: IntArray): Int {
		var max1: Long? = null
		var max2: Long? = null
		var max3: Long? = null
		for (n in nums) {
			val v = n.toLong()
			if (v == max1 || v == max2 || v == max3) continue
			when {
				max1 == null || v > max1 -> { max3 = max2; max2 = max1; max1 = v }
				max2 == null || v > max2 -> { max3 = max2; max2 = v }
				max3 == null || v > max3 -> { max3 = v }
			}
		}
		return if (max3 == null) max1!!.toInt() else max3.toInt()
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
	def thirdMax(self, nums: list[int]) -> int:
		max1 = max2 = max3 = None
		for n in nums:
			if n == max1 or n == max2 or n == max3:
				continue
			if max1 is None or n > max1:
				max3, max2, max1 = max2, max1, n
			elif max2 is None or n > max2:
				max3, max2 = max2, n
			elif max3 is None or n > max3:
				max3 = n
		return max1 if max3 is None else max3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


impl Solution {
	pub fn third_max(nums: Vec<i32>) -> i32 {
		let (mut max1, mut max2, mut max3) = (None, None, None);
		for &n in &nums {
			if Some(n) == max1 || Some(n) == max2 || Some(n) == max3 { continue; }
			if max1.is_none() || n > max1.unwrap() {
				max3 = max2; max2 = max1; max1 = Some(n);
			} else if max2.is_none() || n > max2.unwrap() {
				max3 = max2; max2 = Some(n);
			} else if max3.is_none() || n > max3.unwrap() {
				max3 = Some(n);
			}
		}
		max3.unwrap_or(max1.unwrap())
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


function thirdMax(nums: number[]): number {
	let max1: number|null = null, max2: number|null = null, max3: number|null = null;
	for (const n of nums) {
		if (n === max1 || n === max2 || n === max3) continue;
		if (max1 === null || n > max1) {
			max3 = max2; max2 = max1; max1 = n;
		} else if (max2 === null || n > max2) {
			max3 = max2; max2 = n;
		} else if (max3 === null || n > max3) {
			max3 = n;
		}
	}
	return max3 === null ? max1! : max3;
}

Complexity

⏰ Time complexity: O(n), since we scan the array once.
🧺 Space complexity: O(1), since we only use a constant number of variables.

Third Maximum Number Problem#

Problem#

Examples#

Solution#

Method 1 – Linear Pass#

Intuition#

Approach#

Code#

Complexity#