Skip to main content
Talentd

Third Maximum Number - Solution & Explanation

EasyArraySorting18 min readAsked at: Amazon, Microsoft, Goldman Sachs +6
Practice this problem

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:

Input: nums = [3,2,1]
Output: 1
Explanation:
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
Explanation:
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
Explanation:
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

 

Follow up: Can you find an O(n) solution?

Approach Overview

Problem Overview: Given an integer array, return the third distinct maximum value. If the array has fewer than three distinct values, return the maximum element instead. Duplicate values should be ignored when counting distinct maximums.

Approach 1: Sorting and Distinct Selection (O(n log n) time, O(1) or O(n) space)

Sort the array in descending order and scan for distinct values. After sorting, iterate through the array and count unique numbers until the third distinct value appears. If you reach the end before finding three unique numbers, return the first element (the maximum). The key idea is that sorting groups duplicates together, making it easy to skip them while scanning. This approach is simple and readable but costs O(n log n) time due to the sorting step.

This method works well when simplicity matters more than optimal performance. It relies heavily on sorting behavior and sequential scanning of the array.

Approach 2: Iterative Approach without Extra Space (O(n) time, O(1) space)

Track the top three distinct maximum values while scanning the array once. Maintain three variables: first, second, and third. For each number, skip it if it matches any of these values to enforce distinctness. Otherwise update the three variables by shifting values down whenever a larger number appears.

The core insight: you don't need to sort the entire array to know the three largest distinct numbers. A single pass with careful comparisons maintains the correct ordering. Each element is processed once, giving O(n) time complexity and constant O(1) space.

This approach is optimal for interview scenarios. It demonstrates control over comparisons, handling duplicates, and maintaining ordered state without auxiliary data structures.

Recommended for interviews: The single-pass iterative approach is what most interviewers expect. The sorting solution shows baseline understanding, but the O(n) scan with three variables demonstrates stronger algorithmic thinking and careful handling of edge cases like duplicates and negative numbers.

Approach 1: Sorting and Distinct Selection Approach

This approach involves first sorting the array and then selecting distinct maximums from the sorted array. We can use a set to easily manage distinct elements. After constructing a set, we check if the size of the set is at least 3; if so, we find the third largest by accessing the sorted array of distinct elements, otherwise, return the maximum element.

This C solution uses the C standard library function qsort to sort the array in descending order. We then traverse the sorted array to count distinct elements. We track the number of distinct numbers found and when the count reaches three, we return the number. If we pass through the entire array without finding three distinct maximums, we return the first number.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) as sorting is done in place with qsort.

Try this approach in the editor →

Approach 2: Iterative Approach without Extra Space

This approach keeps track of the three largest distinct numbers iteratively as it processes the array. It uses variables to track them and updates them as it iterates through each number. This way, it can achieve O(n) time complexity without additional set or sorting overhead.

This C solution uses additional variables (initialized to the smallest possible value using LONG_MIN) to track the first, second, and third maximum numbers. During the iteration, if the current number doesn't match the tracked maximums, it updates the respective maximum. At the end of the loop, it checks if the third max was updated from its initialized state, returning it only if so; otherwise, it returns the first maximum.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) because it performs a single pass over the array.
Space Complexity: O(1) as only constant space is used for tracking the maximums.

Try this approach in the editor →

Approach 3: 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.

Then, we iterate through each number in the array. For each number:

  • If it equals any of m_1, m_2, or m_3, we skip this number.
  • If it is greater than m_1, we update the values of m_1, m_2, and m_3 to m_2, m_3, and this number respectively.
  • If it is greater than m_2, we update the values of m_2 and m_3 to m_3 and this number respectively.
  • If it is greater than m_3, we update the value of m_3 to this number.

Finally, if the value of m_3 has not been updated, it means that there is no third largest number in the array, so we return m_1. Otherwise, we return m_3.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Distinct Selection Approach

Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1) as sorting is done in place with qsort.

Iterative Approach without Extra Space

Time Complexity: O(n) because it performs a single pass over the array.
Space Complexity: O(1) as only constant space is used for tracking the maximums.

Single Pass—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Distinct SelectionO(n log n)O(1) or O(n)When readability and quick implementation matter more than optimal runtime
Iterative Three-Max TrackingO(n)O(1)Best general solution; preferred in interviews and large datasets

Video Solution

LeetCode 414. Third Maximum Number Solution Explained - Java • Nick White • 26,487 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Third Maximum Number easy or hard?
Third Maximum Number is classified as an Easy problem on LeetCode. The main challenge is handling duplicates while tracking distinct maximum values. Once you manage the update logic correctly, the optimal O(n) solution becomes straightforward.
Third Maximum Number Python/Java solution
In Python or Java, the most efficient implementation keeps three variables (first, second, third) and updates them during a single traversal of the array. Each number is compared against the tracked values, duplicates are skipped, and the variables shift when a larger number appears.
How to solve Third Maximum Number in O(n)?
Maintain three variables representing the largest, second largest, and third largest distinct numbers. Iterate through the array once and skip numbers already equal to any tracked maximum to ensure distinctness. Update the three variables whenever a larger number appears. After the scan, return the third maximum if it exists, otherwise return the largest value.
What is the best approach for Third Maximum Number?
The best approach is the single-pass iterative method that tracks the top three distinct values. It processes each element once, updating three variables representing the first, second, and third maximum values. This solution runs in O(n) time and uses O(1) extra space, making it optimal for interviews and large arrays.
Is Third Maximum Number asked at Google/Amazon/Meta?
Third Maximum Number is a common screening-style array problem similar to questions asked at companies like Amazon, Google, and Meta. It tests handling duplicates, maintaining running maximum values, and writing efficient single-pass logic without sorting.
What data structure is used in Third Maximum Number?
The optimal solution does not require complex data structures. It uses simple variables to track the three largest distinct numbers during iteration. The alternative solution relies on array sorting, which uses built-in sorting algorithms internally.
What is the time complexity of Third Maximum Number?
Time complexity depends on the approach used. Sorting the array takes O(n log n) time, followed by a linear scan to find the third distinct value. The optimal iterative approach scans the array once and maintains three maximum variables, achieving O(n) time complexity with constant space.

Ready to solve this problem?

Practice Third Maximum Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Kth Largest Element in an Array

Next

Neither Minimum nor Maximum