Third Maximum Number (LeetCode 414): Three Variables, No Sorting

Third Maximum Number (LeetCode 414): Three Variables, No Sorting

Linkjob AI

Third Maximum Number looks like a warm-up, but it hides two traps that interviewers like to probe: duplicates and the "fewer than three distinct values" fallback. Here is a clean way to explain and code it.

Problem

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

Why not just sort?

Sorting and deduplicating works in O(n log n) and is a fine first answer to say out loud. The follow-up is almost always "can you do it in one pass with O(1) space?"

One pass with three slots

def third_max(nums):
first = second = third = None
for x in nums:
if x in (first, second, third):
continue
if first is None or x > first:
first, second, third = x, first, second
elif second is None or x > second:
second, third = x, second
elif third is None or x > third:
third = x
return first if third is None else third

Using None instead of negative infinity matters: the array can contain the smallest 32-bit integer, and a sentinel like -2**31 would make "no third value" and "third value is the minimum" indistinguishable.

Edge cases to mention


  • [2, 2, 3, 1] returns 1, because duplicates of 2 count once.

  • [1, 2] returns 2, the maximum, since there is no third distinct value.

  • [1, 2, -2147483648] returns the minimum integer, which is why the sentinel choice matters.

Generalizing

If the interviewer asks for the k-th distinct maximum, switch to a min-heap of size k plus a set of values already in the heap. That is O(n log k) and reuses the same duplicate check.

Practicing how to talk through traps like these is half of a coding interview. I work on an AI coding interview assistant at Linkjob AI, and this write-up comes from the problems we use to test it.

Report Page