Third Maximum Number
Return the third distinct maximum (or the maximum if fewer than 3 distinct exist) — three running tracker variables.
4 min read
Problem#
Return the third distinct maximum number in the array. If fewer than three distinct values exist, return the maximum.
Examples#
[3,2,1]→1[1,2]→2[2,2,3,1]→1
Constraints#
1 <= nums.length <= 10^4.
Approach#
Three long long slots m1 > m2 > m3 initialized to a sentinel “unset”. Walk; for each x, slot it into the right rank, demoting others, skipping duplicates.
Solution#
class Solution {public: int thirdMax(vector<int>& nums) { long long m1 = LLONG_MIN, m2 = LLONG_MIN, m3 = LLONG_MIN; for (int x : nums) { if (x == m1 || x == m2 || x == m3) continue; if (x > m1) { m3 = m2; m2 = m1; m1 = x; } else if (x > m2) { m3 = m2; m2 = x; } else if (x > m3) { m3 = x; } } return m3 == LLONG_MIN ? (int)m1 : (int)m3; }};import "math"
func thirdMax(nums []int) int { const unset = math.MinInt64 m1, m2, m3 := int64(unset), int64(unset), int64(unset) for _, v := range nums { x := int64(v) if x == m1 || x == m2 || x == m3 { continue } if x > m1 { m3, m2, m1 = m2, m1, x } else if x > m2 { m3, m2 = m2, x } else if x > m3 { m3 = x } } if m3 == unset { return int(m1) } return int(m3)}from typing import List
class Solution: def thirdMax(self, nums: List[int]) -> int: UNSET = float('-inf') m1 = m2 = m3 = UNSET for x in nums: if x == m1 or x == m2 or x == m3: continue if x > m1: m3, m2, m1 = m2, m1, x elif x > m2: m3, m2 = m2, x elif x > m3: m3 = x return int(m1) if m3 == UNSET else int(m3)var thirdMax = function(nums) { let m1 = -Infinity, m2 = -Infinity, m3 = -Infinity; for (const x of nums) { if (x === m1 || x === m2 || x === m3) continue; if (x > m1) { m3 = m2; m2 = m1; m1 = x; } else if (x > m2) { m3 = m2; m2 = x; } else if (x > m3) { m3 = x; } } return m3 === -Infinity ? m1 : m3;};class Solution { public int thirdMax(int[] nums) { long m1 = Long.MIN_VALUE, m2 = Long.MIN_VALUE, m3 = Long.MIN_VALUE; for (int x : nums) { if (x == m1 || x == m2 || x == m3) continue; if (x > m1) { m3 = m2; m2 = m1; m1 = x; } else if (x > m2) { m3 = m2; m2 = x; } else if (x > m3) { m3 = x; } } return m3 == Long.MIN_VALUE ? (int) m1 : (int) m3; }}function thirdMax(nums: number[]): number { let m1: number = -Infinity, m2: number = -Infinity, m3: number = -Infinity; for (const x of nums) { if (x === m1 || x === m2 || x === m3) continue; if (x > m1) { m3 = m2; m2 = m1; m1 = x; } else if (x > m2) { m3 = m2; m2 = x; } else if (x > m3) { m3 = x; } } return m3 === -Infinity ? m1 : m3;}Editorial#
Three running slots beat heap-based solutions for fixed k=3. The dedup check is x == m1 || m2 || m3, since duplicates would otherwise corrupt the slot demotion. LLONG_MIN is a sentinel because INT_MIN is a valid input value.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#