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.

---

Example 1

Input:

nums = [3, 2, 1]

Output:

1

Explanation:
The third distinct maximum number is 1 (since the numbers in descending order are 3, 2, 1).

---

Example 2

Input:

nums = [1, 2]

Output:

2

Explanation:
There are only two distinct numbers. The maximum number is 2.

---

Example 3

Input:

nums = [2, 2, 3, 1]

Output:

1

Explanation:
The distinct numbers in descending order are [3, 2, 1], and the third maximum is 1.

---

Constraints

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

---

Intuition

We are asked to find the third distinct maximum number.
The key word here is distinct, meaning duplicates should be ignored.

We can solve this efficiently without sorting the array completely.

---

Approach 1: Three Variables (O(n) time, O(1) space)

We can keep track of the top three distinct maximum values while iterating through the array.

Steps

1. Initialize three variables to represent the top three unique maximums: firstMax, secondMax, thirdMax
2. For each number num in the array:
   • If num is already equal to one of these max values, skip it (ignore duplicates).
   • If num > firstMax, update all three: thirdMax = secondMax secondMax = firstMax firstMax = num
   • Else if num > secondMax, update: thirdMax = secondMax secondMax = num
   • Else if num > thirdMax, update: thirdMax = num
3. After processing all numbers:
   • If thirdMax was never assigned (still null), return firstMax.
   • Otherwise, return thirdMax.

---

Java Implementation

public class ThirdMaximumNumber {

    public int thirdMax(int[] nums) {
        Long first = null, second = null, third = null;

        for (int num : nums) {
            long n = num; // convert to long to avoid overflow

            if ((first != null && n == first) ||
                (second != null && n == second) ||
                (third != null && n == third)) {
                continue; // skip duplicates
            }

            if (first == null || n > first) {
                third = second;
                second = first;
                first = n;
            } else if (second == null || n > second) {
                third = second;
                second = n;
            } else if (third == null || n > third) {
                third = n;
            }
        }

        return (third == null) ? first.intValue() : third.intValue();
    }

    public static void main(String[] args) {
        ThirdMaximumNumber solver = new ThirdMaximumNumber();
        System.out.println(solver.thirdMax(new int[]{3, 2, 1}));      // Output: 1
        System.out.println(solver.thirdMax(new int[]{1, 2}));         // Output: 2
        System.out.println(solver.thirdMax(new int[]{2, 2, 3, 1}));   // Output: 1
    }
}

---

Dry Run Example

Input: [2, 2, 3, 1]

Step	num	first	second	third	Explanation
1	2	2	null	null	first = 2
2	2	2	null	null	duplicate, skip
3	3	3	2	null	3 > 2, shift
4	1	3	2	1	1 < 2, goes to third

Result: third = 1

---

Approach 2: Using TreeSet (Simpler but O(n log n))

We can use a TreeSet to automatically maintain a sorted collection of distinct elements.

1. Insert all elements into a TreeSet (automatically removes duplicates).
2. If the size of the set is less than 3, return the last (maximum) element.
3. Otherwise, remove the last two largest and return the next (third largest).

---

Java Implementation

import java.util.*;

public class ThirdMaximumNumberSet {

    public int thirdMax(int[] nums) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int num : nums) {
            set.add(num);
            if (set.size() > 3) {
                set.pollFirst(); // keep only top 3 elements
            }
        }

        return set.size() < 3 ? set.last() : set.first();
    }

    public static void main(String[] args) {
        ThirdMaximumNumberSet solver = new ThirdMaximumNumberSet();
        System.out.println(solver.thirdMax(new int[]{3, 2, 1}));      // Output: 1
        System.out.println(solver.thirdMax(new int[]{1, 2}));         // Output: 2
        System.out.println(solver.thirdMax(new int[]{2, 2, 3, 1}));   // Output: 1
    }
}

---

Explanation of TreeSet Method

• TreeSet automatically maintains elements in sorted order.
• We limit its size to 3 using pollFirst() (removes the smallest element).
• At the end:
  • If there are 3 distinct numbers, return the smallest (3rd largest overall).
  • If not, return the largest.

---

Time and Space Complexity

Approach	Time	Space	Description
Three-variable method	O(n)	O(1)	Linear scan, constant space
TreeSet method	O(n log 3) ≈ O(n)	O(3) ≈ O(1)	Logarithmic insertion, fixed size

---

Key Takeaways

1. The three-variable method is the most optimal (O(n) and O(1) space).
2. The TreeSet method is simpler to write but slightly less efficient.
3. The main challenge is correctly handling duplicates.
4. Using Long variables avoids overflow and distinguishes between uninitialized and valid zero values.