Third Maximum Number — Three-Variable O(n) Tracking [LeetCode 414]

Problem Statement#

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

Key word: distinct. Duplicates are collapsed — [2, 2, 3, 1] has distinct values {1, 2, 3}, so the third maximum is 1, not the second 2.

Examples:

Constraints:

• 1 <= nums.length <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

Why This Problem Matters#

This problem looks deceptively easy — "just find the third largest" — but it hides a nasty edge case that trips up the majority of candidates: what if Integer.MIN_VALUE (-2147483648) is in the array?

If you initialise your three sentinel variables to None or float('-inf') in Python that works fine, but in statically-typed languages many people reach for Integer.MIN_VALUE as "not found" sentinel, which then collides with an actual valid array value.

Beyond the gotcha, the problem teaches a broadly reusable pattern: maintaining a fixed-size window of the top-k extremes in a single pass. This exact pattern appears in:

• "Find the kth largest element" (LC 215)
• "Maximum product of three numbers" (LC 628)
• "Find the winner of the circular game" variations
• Any streaming/real-time leaderboard problem where you must track top-k scores without storing all values

Microsoft (where this problem is tagged) uses it as a quick phone-screen filter. Candidates who understand the sentinel trap and articulate the O(n) / O(1) solution clearly pass; those who sort first are asked to optimise.

The Core Insight#

Tracking Three Distinct Maximums#

The goal: maintain three variables first, second, third representing the largest, second-largest, and third-largest distinct values seen so far.

For each number n in the array:

1. Skip duplicates — if n already equals any of the three tracked values, ignore it.
2. Update in order — if n beats first, cascade down: the old first becomes the new second, the old second becomes the new third, and n becomes the new first.
3. Partial updates — if n is between first and second, only second and third shift. If n is between second and third, only third updates.
4. Return — if third was ever set, return it. Otherwise fewer than 3 distinct values exist, so return first.

The Sentinel Trap#

You need a sentinel meaning "this slot has not been filled yet". The tempting choice in typed languages is Integer.MIN_VALUE, but the problem explicitly allows nums[i] to be -2147483648. So the duplicate-skip check n == third would wrongly discard the actual minimum value.

The fix: use Python's None (works perfectly since Python integers are unbounded), or use float('-inf') carefully alongside a separate count, or — in JavaScript — use null. In languages like Java/C++, promote to Long and use Long.MIN_VALUE, which cannot appear in a valid int array.

Visual Dry Run#

Let's trace nums = [2, 2, 3, 1] step by step.

We start with first = -inf, second = -inf, third = -inf (using -inf as "unset").

Step 1 — n = 2

• Is 2 equal to first(-inf), second(-inf), or third(-inf)? No.
• Is 2 > first(-inf)? Yes.
  • third = second = -inf (unchanged)
  • second = first = -inf (unchanged)
  • first = 2

State: first=2, second=-inf, third=-inf

Step 2 — n = 2

• Is 2 equal to first(2)? Yes — skip.

State: first=2, second=-inf, third=-inf (unchanged)

Step 3 — n = 3

• Is 3 equal to first(2), second(-inf), third(-inf)? No.
• Is 3 > first(2)? Yes.
  • third = second = -inf
  • second = first = 2
  • first = 3

State: first=3, second=2, third=-inf

Step 4 — n = 1

• Is 1 equal to first(3), second(2), third(-inf)? No.
• Is 1 > first(3)? No.
• Is 1 > second(2)? No.
• Is 1 > third(-inf)? Yes.
  • third = 1

State: first=3, second=2, third=1

Final check: Is third set? Yes (1). Return third = 1. Correct!

Now trace nums = [1, 2]:

• n=1: first=1
• n=2: first=2, second=1
• third never set. Return first = 2. Correct!

Common Mistakes#

Mistake 1 — Using Integer.MIN_VALUE as sentinel in typed languages#

# WRONG: -2147483648 is a valid input value
first = second = third = -2147483648
 
# If nums = [1, 2, -2147483648]:
# n = -2147483648 matches third == -2147483648 → SKIPPED
# Returns first=2 instead of third=-2147483648

Fix: use None (Python), null (JavaScript), or a count variable to track how many slots are filled.

Mistake 2 — Not skipping duplicates#

Without the duplicate check, [1, 1, 2] would incorrectly treat the second 1 as a new distinct value, making second = 1 and never finding a real third maximum.

# WRONG: missing duplicate skip
for n in nums:
    if n > first:
        third, second, first = second, first, n
    elif n > second:         # 1 > second(-inf) after first=1 is set
        third, second = second, n   # promotes duplicate 1 to second slot

Fix: always add the guard if n in (first, second, third): continue.

Mistake 3 — Wrong cascade order (overwrite before save)#

The order of assignments in the cascade matters enormously:

# WRONG: overwrites second before saving it to third
if n > first:
    second = first  # fine
    first = n       # fine
    third = second  # BUG: second is already the new first!

Fix: update from bottom to top, or use tuple unpacking in Python: third, second, first = second, first, n

Mistake 4 — Off-by-one on the "fewer than 3" fallback#

Some candidates return -inf instead of first when fewer than three distinct values exist, because they check third != -inf but forget that third being unset means "return the maximum (first)".

Solutions#

Approach 1 — Sorted Set (Intuitive, O(n log n))#

Convert to a set (removes duplicates), sort in descending order, and index into position 2.

Python

def thirdMax(nums: list[int]) -> int:
    # Convert to set to eliminate duplicate values
    unique = sorted(set(nums), reverse=True)
    # If at least 3 distinct values exist, return the one at index 2
    # Otherwise return the largest (index 0)
    return unique[2] if len(unique) >= 3 else unique[0]

JavaScript

function thirdMax(nums) {
    // Spread a Set into an array to get unique values
    const unique = [...new Set(nums)].sort((a, b) => b - a);
    // Return third element if it exists, otherwise return the maximum
    return unique.length >= 3 ? unique[2] : unique[0];
}

When to use: When you want readable, concise code and the O(n log n) cost is acceptable. Great for an initial "naive" answer before optimising.

Approach 2 — Three-Variable Single Pass (Optimal, O(n) time, O(1) space)#

Python

def thirdMax(nums: list[int]) -> int:
    # Use None as sentinel — Python None is safe because it can never equal an int
    first = second = third = None
 
    for n in nums:
        # Skip if this value is already tracked (handle duplicates)
        if n == first or n == second or n == third:
            continue
 
        # n beats the current maximum
        if first is None or n > first:
            third = second   # old second drops to third slot
            second = first   # old first drops to second slot
            first = n        # n becomes the new maximum
 
        # n is between first and second
        elif second is None or n > second:
            third = second   # old second drops to third slot
            second = n       # n becomes the new second maximum
 
        # n is between second and third
        elif third is None or n > third:
            third = n        # n becomes the new third maximum
 
    # If third was never set, fewer than 3 distinct values exist → return max
    return third if third is not None else first

JavaScript

function thirdMax(nums) {
    // Use null as sentinel — safe because null !== any number
    let first = null, second = null, third = null;
 
    for (const n of nums) {
        // Skip duplicates — this value is already in one of the three slots
        if (n === first || n === second || n === third) continue;
 
        if (first === null || n > first) {
            // n is the new maximum — cascade everything down one slot
            third = second;
            second = first;
            first = n;
        } else if (second === null || n > second) {
            // n slots between first and second — push third down
            third = second;
            second = n;
        } else if (third === null || n > third) {
            // n slots into the third position
            third = n;
        }
    }
 
    // third === null means fewer than 3 distinct values existed
    return third !== null ? third : first;
}

Why this works: At every step the invariant holds: first >= second >= third and all three are distinct. Duplicates are skipped before any comparison. The cascade always flows top-down so no value is overwritten before it is saved.

Complexity Analysis#

The three-variable approach is strictly better on both dimensions. In practice, for n <= 10^4 the difference is negligible, but interviews expect you to know the optimal.

Follow-up Questions#

These are real questions Microsoft, Amazon, and Google interviewers ask once you solve the base problem:

1. "What if the input is a stream — you cannot store all values?"

The three-variable approach already handles this perfectly. You process one element at a time and maintain only 3 variables. If asked for the kth maximum in a stream for arbitrary k, switch to a min-heap of size k: push each element and pop if the heap exceeds k. The answer is always heap[0].

2. "Generalise to the Nth distinct maximum."

Use a sorted set (like Python's SortedList from sortedcontainers) capped at size N. For each element, insert it; if size exceeds N, pop the minimum. Return the minimum at the end — which is the Nth maximum. Time: O(n log N), Space: O(N).

3. "What if you need the Kth maximum including duplicates (not distinct)?"

This is LeetCode 215 — use a min-heap of size K. The three-variable trick no longer works cleanly because duplicate skipping is wrong for this variant.

4. "Can you solve it without sorting and without extra O(n) space?"

Yes — the three-variable approach does exactly this. Walk the interviewer through it if they push.

5. "What changes if the array can contain Integer.MIN_VALUE?"

This is the sentinel trap. Explain that using Integer.MIN_VALUE as "unset" collides with valid input. In Python, None is safe. In JavaScript, null is safe. In Java/C++, use Long.MIN_VALUE and cast to int only when returning.

This Pattern Solves#

The three-variable cascade is a special case of the top-k tracking pattern. Recognise it when you see:

• "Return the Kth largest/smallest in one pass"
• "Find the maximum product of K numbers from an array"
• "Track the top-K scores in a live stream"
• "Find the Kth order statistic without full sort"

For k = 3 the three variables are hard-coded. For general k, replace them with a min-heap of size k.

The sorted-set approach is the specialisation of the convert, deduplicate, then index pattern — useful when O(n log n) is fine and clarity matters more than speed.

Key Takeaways#

• LeetCode 414 — Third Maximum Number is an Easy problem asked at Amazon and Microsoft; it teaches the sentinel trap and the top-k running-extremes pattern.
• Never use Integer.MIN_VALUE as a "not found" sentinel — the input can contain that value, causing incorrect results; use None/null instead.
• Maintain three nullable variables first, second, third and update them in O(n) time with O(1) space — faster than sorting.
• Skip duplicates explicitly: if the current value equals any of the three tracked maximums, ignore it.
• Sorted set approach (O(n log n) or O(n) with ordered structure) is correct but overkill — mention it as the naive solution then optimize.
• If fewer than three distinct maximums exist, return the first maximum — this edge case catches most wrong answers.
• The top-k running extremes pattern appears in streaming, leaderboard, and sliding-window problems — worth memorizing for interviews at any FAANG company.