How to find Third Maximum Number in given Java array?
Problem Description :
Given integer array nums, return the third 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 third maximum is 1.Example 2 :
Input: nums = [1,2]
Output: 2
Explanation: The third maximum does not exist,
so the maximum (2) is returned instead.Example 3 :
Input: nums = [2,2,3,1]
Output: 1
Explanation: Note that the third maximum here means
the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.In this problem, we have to find 3rd maximum number in given array. If 3rd maximum is not present in array then we have to return maximum number that is present in array. So lets jump on solution and explanation.
Solution 1 : Using Arrays.sort()
class Solution {
public int thirdMax(int[] nums) {
// Sort array
Arrays.sort(nums);
int thirdMaxNumber = nums[nums.length-1];
int temp = 1;
// Traverse array from right to left (Max number to min number)
for (int i = nums.length-1; i > 0 ; i--) {
if (temp == 3) {
break;
}
// Check array values are not same
if (nums[i-1] != thirdMaxNumber) {
thirdMaxNumber = nums[i-1];
++temp;
}
}
// check 3rd max number is present or not
if (temp < 3) {
thirdMaxNumber = nums[nums.length-1];
}
return thirdMaxNumber;
}
}
Solution explanation :
- Sort the given nums array using Arrays.sort() method.
- Declare and assign two int variable : assign last array value to thirdMaxNumber and 1 to temp variable.
- After sort, traverse array from right to left (max number to min number).
- Check if temp variable value is 3 or not. if it is 3 then we break the for loop (After got 3rd max number).
- In second if condition, check if nums[i-1] value are not same as thirdMaxNumber. (because we need third maximum distinct number). If not same then assign nums[i-1] value to thirdMaxNumber and increment temp by one.
- After completion of for loop, check if temp is less than 3. if it is less than 3 that means given array does not contains 3rd max number. so we have to return max number.
Output explanation :
nums = [2, 2, 3, 1]
After Arrays.sort() array becomes :
nums = [1, 2, 2, 3]
- thirdMaxNumber = 3, temp = 1
- i = nums.length-1 | i = 3
- First If.
- temp == 3 | 1 == 3 becomes false.
- Second If
- nums[2] != 3 | 2 != 3 becomes true.
- thirdMaxNumber = nums[2] | thirdMaxNumber = 2
- temp++ | temp = 2
- i = 2, thirdMaxNumber = 2, temp = 2
- 2 == 3 becomes false.
- 1 != 3 becomes true.
- thirdMaxNumber = 1
- temp =3
- i = 3, thirdMaxNumber = 1, temp = 3
- 3 == 3 becomes true and break the for loop.
- temp < 3 | 3 < 3 becomes false.
- return thirdMaxNumber that is 1.
Lets see another solution using Priority Queue.
Learn more about Priority Queue :
Solution 2 : Get 3rd Maximum number using Priority Queue in Java
import java.util.PriorityQueue; class Solution {
public int thirdMax(int[] nums) {
// Get minimum value of integer
int maxNumber = Integer.MIN_VALUE;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for(int i : nums){
// Get maximum number
maxNumber = Math.max(maxNumber, i);
// Add number in priority queue if not exists
if(!pq.contains(i)) {
pq.add(i);
}
// Remove 3rd largest afterward number
if(pq.size() > 3) {
pq.poll();
}
}
// Return 3rd max number if queue size greter than 3
// otherwise return Maximum number of given array
return pq.size() == 3 ? pq.peek() : maxNumber;
}
} Solution explanation :
- Declare an integer number and assign minimum value of integer using Integer.MIN_VALUE.
- Create new PriorityQueue.
- Traverse through given nums array using for each loop.
- Get maximum number from current array index or maxNumber variable.
- If PriorityQueue does not contains array value then add using add() method.
- Remove from PriorityQueue using poll() method, when size becomes greater than 3.
- Return 3rd max number if present otherwise return maximum number of given array.
Output explanation :
nums = [2, 2, 3, 1, 5, 1, 6]
- i = 0, pq = []
- pq does not contains 2. add 2 in pq | pq = [2]
- pq.size() > 3 becomes false.
- i = 1, pq = [2]
- pq contains 2.
- pq.size() > 3 becomes false.
- i = 2, pq = [2]
- pq does not contains 3. add 3 in pq | pq = [2, 3]
- pq.size() > 3 becomes false.
- i = 3, pq = [2, 3]
- pq does not contains 1. add 1 in pq | pq = [1, 3, 2]
- pq.size() > 3 becomes false.
- i = 4, pq = [1, 3, 2]
- pq does not contains 5. add 5 in pq | pq = [1, 3, 2, 5]
- pq.size() > 3 becomes true | Remove from pq | pq = [2, 3, 5]
- i = 5, pq = [2, 3, 5]
- pq does not contains 1 | add 1 in pq | pq = [1, 2, 5, 3]
- pq.size() > 3 becomes true | Remove from pq | pq = [2, 3, 5]
- i = 6, pq = [2, 3, 5]
- pq does not contains 6 | add 6 in pq | pq = [2, 3, 5, 6]
- pq.size() > 3 becomes true | Remove from pq | pq = [3, 6, 5]
- For loop ends
- pg.peek() | return 3
Lets discuss third solution using TreeSet.
Solution 3 : Get 3rd Maximum number using TreeSet in Java
import java.util.TreeSet; class Solution {
public int thirdMax(int[] nums) {
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int n: nums) {
ts.add(n);
// Remove first element if treeset size becomes
// greater than 3
if(ts.size() > 3) {
ts.pollFirst();
}
}
return ts.size() < 3 ? ts.pollLast() : ts.pollFirst();
}
} Key point of TreeSet in Java :
- TreeSet data structure stores unique elements and sorts the elements in ascending order.
Solution explanation :
- Create new TreeSet.
- Traverse through given nums array and store elements one by one. TreeSet stores only unique value so we need not to check if element is already exist or not.
- If TreeSet size becomes greater than 3 then removes first element.
- Return 3rd ma element if TreeSet size is greater than 0, otherwise return max element of given array.
Happy Coding.
Other problem and solution in Java :
Comments
Post a Comment