Third Maximum Number

easy array sorting

Problem

Given an integer array nums, return the third distinct maximum. If fewer than three distinct values exist, return the overall maximum.

Inputnums = [2, 2, 3, 1]

Output1

Distinct values are {1, 2, 3}; the third largest is 1.

nums (comma-separated)

def third_max(nums):
    a = b = c = None
    for x in nums:
        if x in (a, b, c): continue
        if a is None or x > a:    a, b, c = x, a, b
        elif b is None or x > b:  b, c = x, b
        elif c is None or x > c:  c = x
    return c if c is not None else a

function thirdMax(nums) {
  let a = null, b = null, c = null;
  for (const x of nums) {
    if (x === a || x === b || x === c) continue;
    if (a === null || x > a)       { c = b; b = a; a = x; }
    else if (b === null || x > b)  { c = b; b = x; }
    else if (c === null || x > c)  { c = x; }
  }
  return c === null ? a : c;
}

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

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

Explanation

We want the third distinct largest value. Sorting would work, but we can do it in a single pass by remembering just the top three different values we have seen so far.

We keep three slots a > b > c for the largest, second largest, and third largest distinct values, all starting empty. For each number x we first skip it if it equals any slot, because we only count distinct values.

If x beats a, it becomes the new top and the old values cascade down (a shifts to b, b to c). Otherwise if it beats b it slots into second place, or if it beats c it slots into third.

At the end, if c was ever filled we have three distinct values, so we return c. If not, there were fewer than three distinct values, so the problem says return the maximum, which is a.

Example: [2,2,3,1]. We set a=2, skip the duplicate 2, then 3 beats a so it cascades to a=3, b=2, then 1 lands as c=1. The third maximum is 1.

Time: O(n) Space: O(1)