23
Leetcode Array Problem Solutions - Part 7 (Third Maximum Number)
In today's article, we are going to solve another leetcode problem and the statement for today's problem is to the third maximum number from an array.
Link to the problem:-
https://leetcode.com/explore/featured/card/fun-with-arrays/523/conclusion/3231/
Agenda:-
- We are going to sort the array using javascript.
- We will also learn how to remove duplicate elements from an array.
The problem statement is, given an integer array nums, we need to return the third maximum number from the array. If the third maximum does not exist then return the maximum number from the remaining elements.
Let's build a solution to the problem step by step:-
The first thing that comes to our mind is that whenever we try to get the third largest element, it will be much easier if the elements were in a sorted order i.e in ascending order from lowest to highest. In that case what we will do is, if the elements are in sorted order, we can just take the third element from the right end and return it as the third largest element.
So the first thing we do is implement a sort function to rearrange array elements in ascending order:-
const thirdMax = function(nums) {
nums.sort(function(a,b){
return a - b;
});
console.log("sorted array values", nums);
}Next, if the array length is greater than or equal to three we can return the third-last element from the right end. If the length is less than 3 we can return the last element of array as the max element using the pop() method:-
if(nums.length >= 3) {
return nums[nums.length - 3];
} else {
return nums.pop();
}One of the requirements for the solution is that the third largest element should be a distinct one and not a duplicate of another existing element.
This solution works for the default test case but fails when there are duplicates present in the array.
This is because duplicate elements lead to the incorrect index being returned.
To remove duplicates, we can declare a secondary array, in which we add elements from the nums array, but every time we make a push, we will check if the secondary array already contains that value. This way only distinct values will be added to the array as shown below:-
const numsWithoutDuplicates = [];
nums.map((element, index)=>{
if(numsWithoutDuplicates.includes(element) === false) {
numsWithoutDuplicates.push(element);
}
});Once we have removed duplicates we can return third max element from updated array as shown below:-
const thirdMax = function(nums) {
nums.sort(function(a,b){
return a - b;
});
// console.log("sorted array values", nums);
const numsWithoutDuplicates = [];
nums.map((element, index)=>{
if(numsWithoutDuplicates.includes(element) === false) {
numsWithoutDuplicates.push(element);
}
});
// console.log("numsWithoutDuplicates", numsWithoutDuplicates);
if(numsWithoutDuplicates.length >= 3) {
return numsWithoutDuplicates[numsWithoutDuplicates.length - 3];
} else {
return numsWithoutDuplicates.pop();
}
};Now, there might be some better solutions that might reduce the time complexity but I have covered the simplest possible solution that I could think of. As we learn more data structures and algorithms in future, we will try to come up with better solutions.
You can view a video explanation for the problem below:-
If you found this tutorial useful, hit the like button, follow my blog, and if there is anyone you know who will benefit from such articles in data structures in JavaScript or preparing for interviews, please share it with them as well. Goodbye and have a nice day.
Join my discord server for help :
🌐 discord server: https://discord.gg/AWbhSUWWaX
Suggestions and Feedback
🐦 TWITTER: https://twitter.com/saurabhnative
🎥 INSTAGRAM: https://www.instagram.com/saurabhnative/?hl=en
For collaboration, connect with me on Twitter
🐦 TWITTER: https://twitter.com/saurabhnative
Support me on Kofi
23