#414

Easy

LeetCode Problem Workspace

Third Maximum Number

Find the third distinct maximum number in an array using array traversal and sorting techniques, handling duplicates carefully.

array sorting

Problem Statement

Given an integer array nums, return the third distinct maximum number. If it does not exist, return the maximum number. Duplicates are ignored when counting distinct maxima.

For example, in nums = [2,2,3,1], the first distinct maximum is 3, the second is 2, and the third is 1. If nums = [1,2], only two distinct numbers exist, so return 2 as the maximum.

Examples

Example 1

Input: nums = [3,2,1]

Output: 1

The first distinct maximum is 3. The second distinct maximum is 2. The third distinct maximum is 1.

Example 2

Input: nums = [1,2]

Output: 2

The first distinct maximum is 2. The second distinct maximum is 1. The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3

Input: nums = [2,2,3,1]

Output: 1

The first distinct maximum is 3. The second distinct maximum is 2 (both 2's are counted together since they have the same value). The third distinct maximum is 1.

Constraints

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

Solution Approach

Single Pass with Three Variables

Maintain three variables for the top three distinct maximums while iterating. Update these when encountering a new distinct value. This avoids full sorting and handles duplicates efficiently.

Use a Set and Sorting

Insert all numbers into a set to remove duplicates, then sort the set in descending order. Return the third element if it exists, otherwise return the first. This leverages sorting but handles duplicates automatically.

Heap-Based Approach

Use a min-heap of size three to track the largest distinct numbers. Push new numbers only if they are distinct and maintain heap size. The root will be the third maximum if three distinct numbers exist.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(1)

Time complexity is O(N) for a single pass or O(N log N) if sorting is used. Space complexity is O(1) for three variables, or O(N) if using a set or heap to store distinct values.

What Interviewers Usually Probe

Check for duplicate numbers when considering distinct maxima.
Confirm behavior when fewer than three distinct numbers exist.
Clarify whether negative and large integer bounds are supported.

Common Pitfalls or Variants

Common pitfalls

Failing to ignore duplicates and incorrectly counting repeated numbers as distinct.
Sorting the entire array unnecessarily, which increases time complexity.
Not handling the case where fewer than three distinct numbers exist.

Follow-up variants

Find the k-th distinct maximum number in an array, generalizing the approach for any k.
Return both the third maximum and its index in the original array.
Determine the third minimum number with the same array and duplicate constraints.

FAQ

What is the main strategy to find the third maximum number in an array?

Track the top three distinct numbers during a single pass or use a set to remove duplicates before selecting the third maximum.

How do duplicates affect the third maximum calculation?

Duplicates must be ignored; repeated values do not count as distinct maxima.

What should I return if the array has fewer than three distinct numbers?

Return the overall maximum number in the array.

Can this problem be solved without sorting the entire array?

Yes, by maintaining three variables for the top distinct numbers or using a min-heap of size three.

Does the array size or value range impact the solution approach?

Yes, but using a single pass or set-based approach efficiently handles arrays up to 10^4 elements and integers within the given bounds.

terminal

Solution

Solution 1: Single Pass

We can use three variables $m_1$, $m_2$, and $m_3$ to represent the first, second, and third largest numbers in the array respectively. Initially, we set these three variables to negative infinity.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        m1 = m2 = m3 = -inf
        for num in nums:
            if num in [m1, m2, m3]:
                continue
            if num > m1:
                m3, m2, m1 = m2, m1, num
            elif num > m2:
                m3, m2 = m2, num
            elif num > m3:
                m3 = num
        return m3 if m3 != -inf else m1

Continue Practicing

#406 queue reconstruction by height #435 non overlapping intervals #378 kth smallest element in a sorted matrix