O(n) time O(n) space solution to return n-th max

• ``````    public int thirdMax(int[] nums) {
nums = removeDuplicates(nums);
// by changing order value we can get any n-th max
int order = 3;
if(nums.length < order) order = 1;
int f = 0;
int e = nums.length;
while(true) {
int partPoint = partition(nums, f, e);
if(partPoint  == order - 1) return nums[partPoint];
if(partPoint > order - 1) {
e = partPoint;
} else {
f = partPoint;
}
}
}

private int[] removeDuplicates(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int n: nums) {
}
int[] res = new int[set.size()];
int i = 0;
for(int n : set) {
res[i++] = n;
}
return res;
}

private int partition(int[] nums, int f, int e) {
if (e - f == 1) return f;
int pivot = nums[e - 1];
int j = f - 1;
for(int i = f; i < e - 1; i++) {
if(nums[i] >= pivot) {
j += 1;
swap(nums, i, j);
}
}
j += 1;
swap(nums, e - 1, j);
return j;
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}

``````

• In a real interview, they will ask you what if instead of having an array, we now have a number stream?

• They might ask that. But if with this O(n) space solution there is no difference at all as you have a copy of the incoming data.

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