# Java: Use length 3 Array to store Max 3 numbers

• I didn't see a similar solution so I post mine here. Basically I use a length 3 array to store max 3 numbers, and keeping adding to this array if new coming number fulfill therequirement. Return either 3rd element in array or 1st element (<3 elements).

I feel like this is O(n+k) ? Please correct me about Big O, I am not sure about it.

``````public class Solution {
public int thirdMax(int[] nums) {
Integer[] maxThree = new Integer[3];
int currTotal = 0;
for(int i=0; i<nums.length; i++){
int newNum = nums[i];
if(!Arrays.asList(maxThree).contains(newNum)
&&( currTotal<maxThree.length || newNum > maxThree[currTotal-1])){
if(currTotal < maxThree.length){
currTotal ++;
}
int j = currTotal-1;
while(j>0 && maxThree[j-1] < newNum){
maxThree[j]=maxThree[j-1];
j--;
}
maxThree[j]=newNum;
}
}
if(currTotal < maxThree.length){ //3rd max not existed
return maxThree[0];
}
return maxThree[currTotal-1];
}
}
``````

• Besides min-heap and max-heap method, we can use quicksort for kth max.

``````class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
def quicksort(nums, k):
# get kth max num in nums
if len(nums) == k:
return min(nums)
pivot, less, greater = random.choice(nums), [], []
for x in nums:
if x > pivot:
greater.append(x)
elif x < pivot:
less.append(x)
if len(greater) + 1 >= k:
return quicksort([pivot] + greater, k)
else:
return quicksort(less + [pivot], k - len(greater))

nums = set(nums)
if len(nums) < 3:
return max(nums)
return quicksort(nums=list(nums), k=3)
``````

This one is fast, 33ms in Python.

``````class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max1, max2, max3 = -sys.maxint, -sys.maxint, -sys.maxint
for x in nums:
if x > max1:
max1, max2, max3 = x, max1, max2
elif max1 > x > max2:
max2, max3 = x, max2
elif max2 > x > max3:
max3 = x
return max3 if max3 != -sys.maxint else max1
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.