public int thirdMax(int[] nums) {
Integer max1 = null;
Integer max2 = null;
Integer max3 = null;
for (Integer n : nums) {
if (n.equals(max1)  n.equals(max2)  n.equals(max3)) continue;
if (max1 == null  n > max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (max2 == null  n > max2) {
max3 = max2;
max2 = n;
} else if (max3 == null  n > max3) {
max3 = n;
}
}
return max3 == null ? max1 : max3;
}
Java neat and easy understand solution, O(n) time, O(1) space


@jdrogin Yes, I think initialize variables with Integer.MIN_VALUE is not a good idea in this case.

@yuxiaofei2016 This is best solution I have seen so far. Thanks.
Would you explain why iniitializing variables with Integer.MIN_VALUE is not a good idea?

@spencerL Because once you initializing them with Integer.MIN_VALUE, you have to add more logic to figure out the value from the initialization or from the array.

@jakeybear41 the solution uses Integer instead of int because it is a nullable type. This way you can use null as a check for "not set", alternately you could use additional bools for this but Integer is a nice way to keep it all together.


@jakeybear41 If you use == to compare Integer you will be comparing references not values. you could use a.intValue() == b.intValue() to compare values.


If i were the interviewer I would ask "what is not ideal about this solution?"
And the answer I expect would be that it's not easily modifiable, for example if you want to find 7th maximum instead of 3rd.
I like the answers using dynamic data structures more because of that reason. (I used a linked list)


A similar but alternative way:
public class Solution { public int thirdMax(int[] nums) { Integer[] largest = new Integer[3]; for (int n: nums) { if (largest[0] == null  n > largest[0]) { largest[2] = largest[1]; largest[1] = largest[0]; largest[0] = n; } else if (largest[0] != null && largest[0] > n && (largest[1] == null  n > largest[1])) { largest[2] = largest[1]; largest[1] = n; } else if (largest[1] != null && largest[1] > n && (largest[2] == null  n > largest[2])) { largest[2] = n; } } return largest[2] == null? largest[0]: largest[2]; } }

"elseif" is magic!
I consider it using separated if logic and code just went very messy!public class Solution { public int thirdMax(int[] nums) { Integer max = null, secondMax = null, thirdMax = null; for(int num : nums) { if((max != null && max == num)  (secondMax != null && secondMax == num)  (thirdMax != null && thirdMax == null)) { continue; } if(max == null  max < num) { thirdMax = secondMax; secondMax = max; max = num; continue; } if((secondMax == null && num < max)  (secondMax != null && num < max && num > secondMax)) { thirdMax = secondMax; secondMax = num; continue; } if((thirdMax == null && num < secondMax)  (thirdMax != null && num < secondMax && num > thirdMax)) { thirdMax = num; continue; } } if(thirdMax != null) return thirdMax; else return max; } }

I have the same idea with you. I wrote it in C++
class Solution { public: int thirdMax(vector<int>& nums) { long long mx, sec, thr; mx = sec = thr = LONG_MIN; for (int i = 0; i < nums.size(); i++) { if (nums[i] == mx  nums[i] == sec  nums[i] <= thr) { continue; } if (nums[i] > mx) { thr = sec; sec = mx; mx = nums[i]; } else if (nums[i] > sec) { thr = sec; sec = nums[i]; } else if (nums[i] > thr) { thr = nums[i]; } } return thr == LONG_MIN ? mx : thr; } };