Leetcode kth largest element without using heaps

Question

I was working on kth largest element problem on leetcode

Question

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

My Solution

I'm basically setting every max element in array to Minimum possible integer and doing this k times.

Then i just calculate the maximum value in the array.

class Solution {
 public int findKthLargest(int[] nums, int k) {
 for(int i = 0; i < k-1; i++){
 replaceLargestWithMin(nums);
 }
 return findLargest(nums);
 }
 
 //TC: O(N)
 public void replaceLargestWithMin(int[] nums){
 // O(N)
 int currMax = findLargest(nums);
 // O(N)
 for(int i = nums.length - 1; i >= 0; i--){
 if(nums[i] == currMax){
 nums[i] = Integer.MIN_VALUE;
 break;
 }
 }
 }
 
 //TC: O(N)
 public int findLargest(int[] nums){
 int max = nums[0];
 for(int num : nums){
 max = Math.max(max, num);
 }
 return max;
 }
}

As per my understanding the time complexity of solution will be kO(n) ~ O(n) which is same for heap solution.

However, the above solution is performing in the lower 5 percentile solutions in java.

Is this solution not in O(n)? Am I calculating the time complexity incorrectly?

EDIT:

Updated solution after doing changes suggested by vvotan in comments:

class Solution {
 public int findKthLargest(int[] nums, int k) {
 for(int i = 0; i < k-1; i++){
 replaceLargestWithMin(nums);
 }
 return nums[findLargest(nums)];
 }
 
 public void replaceLargestWithMin(int[] nums){
 nums[findLargest(nums)] = Integer.MIN_VALUE;
 }
 
 public int findLargest(int[] nums){
 int maxIndex = 0;
 for(int i = 0; i < nums.length; i++){
 if(nums[maxIndex] < nums[i]){
 maxIndex = i;
 }
 }
 return maxIndex;
 }
}

This increases the overall performance (only tested on leetcode) ~ 15%

• vnp: Am I calculating the time complexity incorrectly? - Yes. You presume that k is fixed (or small compared to n). Only then the conclusion kO(n) ~ O(n) holds. In the worst case k ~ n the time complexity degrades to \$O(n^2)\$.
• vvotan: you've jus found the largest value, why are you searching for it again? Make findLargest return the position of the larges element
• D_S_X: @vnp That makes sense. But the solution using heap has time complexity of O(Nlogk). How is that better than a simple sorting solution i.e. O(NlogN). Why are heaps the go to solution for these problems?
• vvotan: @D_S_X, in replaceLargestWithMin you are finding the maximum value by looking through the whole array. Then you are looking through the whole array again until you find that same value again to replace it. But you already knew where it was, just chose to ignore that information.
• pacmaninbw: There is a bot that runs that finds edits after a question is answered. Rather than editing in the future after an answer has been provided, it might be better if you either posted your own answer or provided a followup question with a link to the previous question. It might also have been better if @vvotan had posted an answer rather than a comment.

Answer 1

You need to be observant of the bounds in the problem description, in particular they allow k=n which means your worst case time complexity is not constant k times O(n), it's actually O(kn), and when k is approximately n, then it turns into O(n^2).

I solved a similar problem a while ago and did some interesting benchmarking. I'm not sure why you don't want to use a heap which is the obvious solution but I showed that insertion sort works well for moderately big k.

Edit: Why is using a heap preferred over sort and pick k'th element?

Excellent question, for a heap you only need to keep a heap of size K as you can always drop the smallest element and add a new, larger element from the input and get correct result. This yields time complexity of O(nlog(k)) as opposed to O(nlog(n)) for sort and pick. However note that for the heap you only need O(k) memory instead of O(n). Indeed when n=k sort and pick using quicksort is expected to be superior to a heap because quicksort is generally faster even though they have the same big-O behaviour. However in the case of this particular problem, it's reasonable to expect that k is notably smaller than n most of the time so we expect the heap to be better. But these are just qualified guesses, you really should try both and benchmark.

• D_S_X: Thanks, yeah i understand why my solution is performing so. But in case k = n, won't heap solution O(Nlogk) take O(NlogN) which is same as a simple sort and fetch kth element solution? Why is heap preferred over sorting solution?
• Emily L.: @D_S_X I updated my answer, ptal
• Kelly Bundy: "not kO(n), it's actually O(kn)" - Aren't they the same?
• D_S_X: @KellyBundy It says f.O(g) = O(fg) so i guess they're the same right?
• pacmaninbw: Nice to see you are still providing good answers!

Answer 2

It is possible to achieve a much better performance in a brutal way result with the use of auxiliary sorted k size array obtained copying and ordering the first k elements from your nums array:

int length = nums.length;
int lastIndex = k - 1; 
int[] arr = Arrays.copyOf(nums, k);
Arrays.sort(arr);

Once you initialized the arr array for every remaining element in the nums array you can check if it is lesser than arr[0] and if the answer is positive you can insert the new element in the 0 position and swapping the adiacent elements to reorder the array :

for (int i = k; i < length; ++i) {
 if (nums[i] > arr[0]) { //<.-- elements minor than arr[0] will be excluded
 arr[0] = nums[i];
 for (int j = 1; j < k && arr[j - 1] > arr[j]; ++j) {
 int tmp = arr[j - 1];
 arr[j - 1] = arr[j];
 arr[j] = tmp;
 }
 }
}

The final code of the method :

public static int findKthLargest(int[] nums, int k) {
 int length = nums.length;
 int lastIndex = k - 1; 
 int[] arr = Arrays.copyOf(nums, k);
 Arrays.sort(arr);
 
 for (int i = k; i < length; ++i) {
 if (nums[i] > arr[0]) { 
 arr[0] = nums[i];
 for (int j = 1; j < k && arr[j - 1] > arr[j]; ++j) {
 int tmp = arr[j - 1];
 arr[j - 1] = arr[j];
 arr[j] = tmp;
 }
 }
 }
 
 return arr[0];
}

Note that this solution is not an optimal solution, like stated in Emily L.'s answer use of heaps can help you to improve performance.

• D_S_X: Nice approach!! I wish they had better set of test cases on leetcode to showcase which solutions is better. Oddly enough your solution runs slightly faster than heap solution. Also, simply sorting the nums and fetching kth element runs faster than both :)
• dariosicily: @D_S_X Thank you :), as you said I think it depends from showcases used in the leetcode site. About my solution, to erase elements exchange once you know the position i of your new element, you could overwrite the 0..i-1 elements with the 1..i elements and write the new element in the i position.