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%

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.

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.