Problem Statement
This problem is from Leetcode – Third Maximum Number. The problem statement is as below:
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.
Solution
Let find the max value first by looping through the array. Now we can simply ignore this max value in the array and again find the max value. This will give us the second max value. Again, ignore the max and second max values in the array and find the max. This will give us the third max value. see the code sample below:
public int thirdMax(int[] nums) {
// initialize the three max variables to min val
int max = Integer.MIN_VALUE;
int secondMax = Integer.MIN_VALUE;
int thirdMax = Integer.MIN_VALUE;
int curNum = 0;
boolean isTmax = false;
// find max val
for(int i=0; i<nums.length;i ++) {
curNum = nums[i];
if(max <= curNum) {
max = curNum;
}
}
/*
* Now iterate the array again while ignoring the max val above.
* The max val of this array will be the second max
*/
for(int i=0; i<nums.length;i ++) {
curNum = nums[i];
if(curNum != max) {
if(secondMax <= curNum) {
secondMax = curNum;
}
}
}
/*
* Iterate the array again while ignoring the max and second max val above.
* The max val of this array will be the third max
*/
for(int i=0; i<nums.length;i ++) {
curNum = nums[i];
if(curNum != max && curNum != secondMax) {
if(thirdMax <= curNum) {
thirdMax = curNum;
isTmax = true;
}
}
}
if(!isTmax) {
thirdMax = max;
}
return thirdMax;
}
You can checkout the code from Github here: Third Maximum Number. See the performance of this approach below:
