Third Maximum Number solution and explanation
Google
TCS
9 more videos on this problem
LeetCode 414. Third Maximum Number Solution Explained - JavaNick White · 6:46 · 26K views
414. Third Maximum Number | LEETCODE EASYcode Explainer · 2:43 · 6K views
Third Maximum Number | LeetCode 414 | Coding Interview TutorialTerrible Whiteboard · 10:52 · 6K views
414. Third Maximum Number || In Java || Leetcode || Easy Way #leetcodeQuick Learning With Sree · 5:58 · 5K views
Leetcode 414: Third Maximum Number | Step-by-Step SolutionMohit Chhabra · 15:11 · 3K views
LeetCode Problem 414. Third Maximum Number || Java Solution WalkthroughUnknown Koder · 6:19 · 2K views
LeetCode 414 : Third Maximum Number || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 15:55 · 1K views
414. Third Maximum Number (Leetcode Easy)Programming Live with Larry · 14:37 · 1K views
414. Third Maximum Number | Leetcode | PythonAbdullah Arshed · 1:58 · 1K views
414. Third Maximum Number (Leetcode Solution)Varun Agarwal · 15:01 · 1K views
The problem
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
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.
def thirdMax(nums):
distinct_nums = set(nums)
if len(distinct_nums) < 3:
return max(distinct_nums)
distinct_nums.remove(max(distinct_nums))
distinct_nums.remove(max(distinct_nums))
return max(distinct_nums)
print(thirdMax([2, 2, 3, 1]))import java.util.TreeSet;
public class Solution {
public int thirdMax(int[] nums) {
TreeSet<Integer> distinctSet = new TreeSet<>();
for (int num : nums) {
distinctSet.add(num);
if (distinctSet.size() > 3) {
distinctSet.pollFirst();
}
}
return distinctSet.size() < 3 ? distinctSet.last() : distinctSet.first();
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 2, 3, 1};
System.out.println(sol.thirdMax(nums));
}
}#include <iostream>
#include <vector>
#include <set>
int thirdMax(std::vector<int>& nums) {
std::set<int> distinctSet(nums.begin(), nums.end());
if (distinctSet.size() < 3) return *distinctSet.rbegin();
for (int i = 0; i < 2; ++i) distinctSet.erase(--distinctSet.end());
return *distinctSet.rbegin();
}
int main() {
std::vector<int> nums = {2, 2, 3, 1};
std::cout << thirdMax(nums) << std::endl;
return 0;
}const thirdMax = function(nums) {
const distinctNums = [...new Set(nums)].sort((a, b) => b - a);
return distinctNums.length < 3 ? distinctNums[0] : distinctNums[2];
};
console.log(thirdMax([2, 2, 3, 1]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int thirdMax(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int distinctCount = 1;
int currentMax = nums[0];
for (int i = 1; i < numsSize; i++) {
if (nums[i] != currentMax) {
distinctCount++;
currentMax = nums[i];
if (distinctCount == 3) {
return nums[i];
}
}
}
return nums[0];
}
int main() {
int nums[] = {2, 2, 3, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", thirdMax(nums, size));
return 0;
}using System;
using System.Linq;
public class Solution {
public int ThirdMax(int[] nums) {
var distinctNums = nums.Distinct().OrderByDescending(x => x).ToList();
return distinctNums.Count < 3 ? distinctNums.Max() : distinctNums[2];
}
public static void Main(string[] args) {
var solution = new Solution();
int[] nums = {2, 2, 3, 1};
Console.WriteLine(solution.ThirdMax(nums));
}
}In the Python solution, we convert the list to a set for unique elements. We check for the size of the set; if it's less than three, we return the maximum. Otherwise, we remove the two largest distinct elements and return the next maximum which is the third distinct maximum.
Time Complexity: O(n) for converting a list to a set and finding max values.
Space Complexity: O(n) due to the set storing unique elements.
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.
def thirdMax(nums):
first = second = third = float('-inf')
for num in nums:
if num in (first, second, third):
continue
if num > first:
third, second, first = second, first, num
elif num > second:
third, second = second, num
elif num > third:
third = num
return first if third == float('-inf') else third
print(thirdMax([2, 2, 3, 1]))import static java.lang.Long.MIN_VALUE;
public class Solution {
public int thirdMax(int[] nums) {
long first = MIN_VALUE, second = MIN_VALUE, third = MIN_VALUE;
for (int num : nums) {
if (num == first || num == second || num == third) continue;
if (num > first) {
third = second;
second = first;
first = num;
} else if (num > second) {
third = second;
second = num;
} else if (num > third) {
third = num;
}
}
return third == MIN_VALUE ? (int) first : (int) third;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {2, 2, 3, 1};
System.out.println(solution.thirdMax(nums));
}
}#include <iostream>
#include <limits>
#include <vector>
int thirdMax(std::vector<int>& nums) {
long first = LLONG_MIN, second = LLONG_MIN, third = LLONG_MIN;
for (int num : nums) {
if (num == first || num == second || num == third) continue;
if (num > first) {
third = second;
second = first;
first = num;
} else if (num > second) {
third = second;
second = num;
} else if (num > third) {
third = num;
}
}
return third == LLONG_MIN ? first : third;
}
int main() {
std::vector<int> nums = {2, 2, 3, 1};
std::cout << thirdMax(nums) << std::endl;
return 0;
}const thirdMax = function(nums) {
let first = -Infinity, second = -Infinity, third = -Infinity;
for (let num of nums) {
if (num === first || num === second || num === third) continue;
if (num > first) {
[third, second, first] = [second, first, num];
} else if (num > second) {
[third, second] = [second, num];
} else if (num > third) {
third = num;
}
}
return third === -Infinity ? first : third;
};
console.log(thirdMax([2, 2, 3, 1]));#include <stdio.h>
#include <limits.h>
int thirdMax(int* nums, int numsSize) {
long first = LONG_MIN, second = LONG_MIN, third = LONG_MIN;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == first || nums[i] == second || nums[i] == third) continue;
if (nums[i] > first) {
third = second;
second = first;
first = nums[i];
} else if (nums[i] > second) {
third = second;
second = nums[i];
} else if (nums[i] > third) {
third = nums[i];
}
}
return third == LONG_MIN ? (int)first : (int)third;
}
int main() {
int nums[] = {2, 2, 3, 1};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", thirdMax(nums, size));
return 0;
}using System;
public class Solution {
public int ThirdMax(int[] nums) {
long first = long.MinValue, second = long.MinValue, third = long.MinValue;
foreach (int num in nums) {
if (num == first || num == second || num == third) continue;
if (num > first) {
third = second;
second = first;
first = num;
} else if (num > second) {
third = second;
second = num;
} else if (num > third) {
third = num;
}
}
return third == long.MinValue ? (int)first : (int)third;
}
public static void Main(string[] args) {
var solution = new Solution();
Console.WriteLine(solution.ThirdMax(new int[]{2, 2, 3, 1}));
}
}Python uses negative infinity for initial state and efficiently updates first, second, and third variables akin to the logic of replacing as larger numbers are encountered in a single pass of the list. The third result reflects any real third distinct maximum conditionally discovered as the list was traversed.
Time Complexity: O(n) due to the single pass loop of nums.
Space Complexity: O(1) due to the fixed storage for tracking three maximums.
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, orm_3, we skip this number. - If it is greater than
m_1, we update the values ofm_1,m_2, andm_3tom_2,m_3, and this number respectively. - If it is greater than
m_2, we update the values ofm_2andm_3tom_3and this number respectively. - If it is greater than
m_3, we update the value ofm_3to 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).
func thirdMax(nums []int) int {
m1, m2, m3 := math.MinInt64, math.MinInt64, math.MinInt64
for _, num := range nums {
if num == m1 || num == m2 || num == m3 {
continue
}
if num > m1 {
m3, m2, m1 = m2, m1, num
} else if num > m2 {
m3, m2 = m2, num
} else if num > m3 {
m3 = num
}
}
if m3 != math.MinInt64 {
return m3
}
return m1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting and Distinct Selection Approach | Time Complexity: O(n) for converting a list to a set and finding max values. |
| Iterative Approach without Extra Space | Time Complexity: O(n) due to the single pass loop of nums. |
| Single Pass | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Distinct Selection | O(n log n) | O(1) or O(n) | When readability and quick implementation matter more than optimal runtime |
| Iterative Three-Max Tracking | O(n) | O(1) | Best general solution; preferred in interviews and large datasets |
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.