Third Maximum Number (LeetCode 414): Three Variables, No Sorting
Linkjob AIThird 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 thirdUsing 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.