Third Maximum Number — OrderedSet O(n) [Microsoft Easy]

Problem Statement

Given an integer array nums, return the third distinct maximum. If it does not exist, return the maximum.

Input: [3,2,1] → 1 | [1,2] → 2 | [2,2,3,1] → 1

Intuition
C++ Solution
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time, O(1) space (3-variable) or O(n log n) (sort approach)

Intuition

Track three variables first, second, third (distinct maxima). Walk the array, updating them in order. Use None/INT_MIN as sentinels for "not yet found".

C++ Solution

class Solution {
public:
    int thirdMax(vector<int>& nums) {
        long long a = LLONG_MIN, b = LLONG_MIN, c = LLONG_MIN;
        for (long long n : nums) {
            if (n == a || n == b || n == c) continue;
            if (n > a) { c = b; b = a; a = n; }
            else if (n > b) { c = b; b = n; }
            else if (n > c) { c = n; }
        }
        return (int)(c == LLONG_MIN ? a : c);
    }
};

Java Solution

class Solution {
    public int thirdMax(int[] nums) {
        Long a = null, b = null, c = null;
        for (long n : nums) {
            if (n == a || n == b || n == c) continue;
            if (a == null || n > a) { c = b; b = a; a = n; }
            else if (b == null || n > b) { c = b; b = n; }
            else if (c == null || n > c) { c = n; }
        }
        return (int)(c == null ? a : c);
    }
}

Python Solution

def thirdMax(nums):
    top = sorted(set(nums), reverse=True)
    return top[2] if len(top) >= 3 else top[0]

JavaScript Solution

function thirdMax(nums) {
    const top = [...new Set(nums)].sort((a,b) => b-a);
    return top.length >= 3 ? top[2] : top[0];
}