Log inSign up
easyLeetCodeNot Started

Third Maximum Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an integer array nums, return *the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number*.

Example 1 · Standard 3-element Array:

Input: nums = [3, 2, 1]
Output: 1
Explanation: The first distinct maximum is 3, the second is 2, and the third is 1.

Example 2 · Array with Only 2 Distinct Values:

Input: nums = [1, 2]
Output: 2
Explanation: The first distinct maximum is 2, the second is 1. The third maximum does not exist, so the maximum (2) is returned.

Example 3 · Array with Duplicates:

Input: nums = [2, 2, 3, 1]
Output: 1
Explanation: The distinct values are 3, 2, and 1. The first maximum is 3, second is 2 (both 2s count as one distinct value), and third is 1.

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Tracking multiple extrema variables simultaneously
  • Handling duplicates in distinct top-k queries
  • 64-bit integer limits vs null pointers for boundary conditions

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Maintain multiple distinct extrema variables (first, second, third) with cascading updates.
  • Handle 32-bit integer minimum value -2^31 cleanly using null wrappers or 64-bit integers.
  • Eliminate duplicates in linear time without creating auxiliary sets.
  • Write robust code across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Asked for the k-th distinct maximum element where k is small and fixed (k = 3).
  • Duplicates must not occupy multiple ranks.
  • Requires single-pass O(N) time and strictly O(1) auxiliary space.

Algorithmic Decision Tree:

  • Whenever k is small and constant (k <= 3): Maintain k distinct variables and cascade them in a single linear pass instead of allocating a Heap or sorting.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Remove Duplicates & Sort Descending

Intuition

Insert all elements into a Set to eliminate duplicates, sort in descending order, and return 3rd element (or 1st).

Algorithm

  1. 1. Collect unique elements into list unique.
  2. 2. Sort unique descending: unique.sort((a, b) => b - a).
  3. 3. If unique.length >= 3, return unique[2]; else return unique[0].

Distinct Set + Descending Sort

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Duplicate numbers are filtered out
Visual state
Values and pointers at this exact step
array
S
3
2
1
0
1
2
Variables at this step
distinctCount
3
set
[3,2,1]
Check / comparison
Collect unique values into Set: Set {3, 2, 1}
Decision / next transition
Set size = 3 distinct values.
Why this step matters

Duplicate numbers are filtered out.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int thirdMax(vector<int>& nums) {
17 set<int, greater<int>> unique(nums.begin(), nums.end());
18 if (unique.size() < 3) return *unique.begin();
19 auto it = unique.begin();
20 advance(it, 2);
21 return *it;
22 }
23};
24
25int main() {
26 Solution sol;
27 vector<int> nums = {2, 2, 3, 1};
28 int ans = sol.thirdMax(nums);
29 cout << "Third Max: " << ans << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N log N) — Deduplication takes O(N) and sorting unique elements takes O(N log N).
  • Space complexity: O(N) — Set and unique list take O(N) memory.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Min-Heap of Size 3 with Set Tracking

Intuition

Maintain a Min-Heap of at most 3 distinct maximum elements.

Algorithm

  1. 1. Maintain min-heap of size at most 3 and set seen.
  2. 2. For each num in nums: - If seen.has(num), continue. - seen.add(num), heap.push(num). - If heap.size() > 3, seen.remove(heap.pop()).
  3. 3. If heap.size() == 3, return heap.top(); else return max of heap.

Min-Heap of Size 3 with Set Tracking

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
3 is currently the only element in the heap
Visual state
Values and pointers at this exact step
heap
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
3
0
↑ root
Binary Heap Tree Topology
3#0
Variables at this step
heap
[3]
heapSize
1
Check / comparison
Insert 3 into min-heap: heap = [3]
Decision / next transition
Heap size = 1 <= 3. Keep 3.
Why this step matters

3 is currently the only element in the heap.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int thirdMax(vector<int>& nums) {
17 unordered_set<int> seen;
18 priority_queue<int, vector<int>, greater<int>> minHeap;
19
20 for (int num : nums) {
21 if (seen.insert(num).second) {
22 minHeap.push(num);
23 if (minHeap.size() > 3) minHeap.pop();
24 }
25 }
26
27 if (minHeap.size() == 3) return minHeap.top();
28 if (minHeap.size() == 2) { minHeap.pop(); return minHeap.top(); }
29 return minHeap.top();
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<int> nums = {2, 2, 3, 1};
36 int ans = sol.thirdMax(nums);
37 cout << "Third Max: " << ans << endl;
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(N log 3) = O(N) — Heap size is bounded by 3, so each insertion/pop takes O(log 3) = O(1) time.
  • Space complexity: O(1) — Heap and set store at most 3 integers, consuming O(1) memory.

3. Three Dedicated Maximum Trackers (Optimal & Standard)

Intuition

Track the 1st, 2nd, and 3rd maximums using 3 scalar variables in a single pass.

Algorithm

  1. 1. Initialize first = null, second = null, third = null.
  2. 2. For each num in nums: - If num is equal to first, second, or third, continue. - If first is null or num > first: third = second, second = first, first = num - Else if second is null or num > second: third = second, second = num - Else if third is null or num > third: third = num.
  3. 3. If third != null return third; else return first.

Three Dedicated Maximum Trackers (Single Pass)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
First number becomes current top maximum
Visual state
Values and pointers at this exact step
array
S
3
2
1
0
↑ i=0
1
2
Variables at this step
max1
3
max2
null
max3
null
Check / comparison
x = 3: greater than max1 (null)
Decision / next transition
Cascade: max3 = max2, max2 = max1, max1 = 3.
Why this step matters

First number becomes current top maximum.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 int thirdMax(vector<int>& nums) {
17 long long first = LLONG_MIN, second = LLONG_MIN, third = LLONG_MIN;
18
19 for (int num : nums) {
20 if (num == first || num == second || num == third) continue;
21
22 if (num > first) {
23 third = second;
24 second = first;
25 first = num;
26 } else if (num > second) {
27 third = second;
28 second = num;
29 } else if (num > third) {
30 third = num;
31 }
32 }
33 return third == LLONG_MIN ? first : third;
34 }
35};
36
37int main() {
38 Solution sol;
39 vector<int> nums = {2, 2, 3, 1};
40 int ans = sol.thirdMax(nums);
41 cout << "Third Max: " << ans << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N) — Single linear traversal with O(1) variable assignments.
  • Space complexity: O(1) — Only 3 scalar variables are maintained. Auxiliary space is strictly O(1).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Remove Duplicates & Sort DescendingO(N log N)O(N)Insert all elements into a Set to eliminate duplicates, sort in descending order, and return 3rd element (or 1st).Repeated redundant scans over the input.
2.Approach 2: Min-Heap of Size 3 with Set TrackingO(N log 3) = O(N)O(1)Maintain a Min-Heap of at most 3 distinct maximum elements.Auxiliary memory allocation or sorting step.
3.Approach 3: Three Dedicated Maximum Trackers (Optimal & Standard)OptimalO(N)O(1)Track the 1st, 2nd, and 3rd maximums using 3 scalar variables in a single pass.None. Asymptotically optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Array with Integer Minimum Value — Input: nums = [1, 2, -2147483648], Expected: -2147483648 — Using 64-bit LLONG_MIN in C++ or Integer objects in Java prevents collision with -2^31.
  • Array with Only 2 Distinct Elements — Input: nums = [1, 2], Expected: 2 — third is null, so function must return first (2).
  • All Elements Identical — Input: nums = [5, 5, 5, 5], Expected: 5 — Only 1 distinct element; returns 5.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Third Maximum Number?

2.Why is the brute force approach suboptimal for large inputs in Third Maximum Number?

3.Which data structure or technique enables the optimal solution for Third Maximum Number?

Back to DSA Sheet