← Back to Index

📚 Third Maximum Number – Java Cheat Sheet

📌 What Is It?

The Third Maximum Number problem involves finding the third distinct maximum number in an array. If the third maximum does not exist, return the maximum number.

This problem can be solved using a set or a min-heap to track distinct maximum numbers.

🧱 Pattern Template

class Solution {
    public int thirdMax(int[] nums) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        Set<Integer> seen = new HashSet<>();

        for (int num : nums) {
            if (!seen.contains(num)) {
                seen.add(num);
                minHeap.offer(num);
                if (minHeap.size() > 3) {
                    minHeap.poll(); // Remove the smallest element
                }
            }
        }

        // If there are less than 3 distinct numbers, return the maximum
        if (minHeap.size() < 3) {
            while (minHeap.size() > 1) {
                minHeap.poll();
            }
        }

        return minHeap.peek();
    }
}

📊 Time Complexity

• Heap Operations: O(N log 3) – Adding and removing elements from the heap.
• Overall Complexity: O(N log 3).

✅ Use Cases

• Finding the third distinct maximum number in an array
• Efficiently processing large datasets
• Applications in ranking and leaderboard systems

📘 Common LeetCode Problems

• 414. Third Maximum Number [Easy] Heap

🧪 Example: Third Maximum Number

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

Explanation:
- The distinct maximum numbers are [3, 2, 1].
- The third maximum number is 1.

▶️ View Animation

💡 Pro Tips

• Use a set to track distinct numbers and a min-heap to efficiently find the third maximum.
• Edge cases: arrays with less than 3 distinct numbers.
• Ensure the heap size is limited to 3 for optimal performance.