Problem

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

Solution

There are many solutions possible. Here are some we will discuss:

  • Bubble k times
  • temporary array of size k to store largest k elements
  • Sorting

Method 1 - Use Bubble K Times

  1. Modify Bubble Sort to run the outer loop at most k times.
  2. Print the last k elements of the array obtained in step 1. Time Complexity: O(nk) Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

Method 2 - Use Temporary Array of Size K

  1. Store the first k elements in a temporary array temp[0..k-1]
  2. Find the smallest element in temp[], let the smallest element be min.
  3. For each element x in arr[k] to arr[n-1] If x is greater than the min then remove min from temp[] and insert x.
  4. Print final k elements of temp[] Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)

Method 3 - Use Sorting

  1. Sort the elements in descending order in O(nLogn)
  2. Print the first k numbers of the sorted array O(k).
public int findKthLargest(int[] nums, int k) {
	 Arrays.sort(nums);
	 return nums[nums.length-k];
}

Time complexity: O(nlogn)

Method 4 - Tournament Principle

We have to find the element which has competed with largest element, and is just (k-1)th level. We have discussed this principle here.

Method 5 - Using Max Heap (Heap Select)

Consider the array of length n. Here is the algo :

  • Build a max heap in O(n) ;
  • Now remove k elements from the heap; wherein each removal costs log(n) time to maintain the heap property. So total time complexity = O(k logn)

Time complexity: O(n + klogn)

public static int find(int[] A, int k) {
	PriorityQueue<Integer> pq = new PriorityQueue<Integer> (Collections.reverseOrder());
	for (int i = 0; i<A.length; i++) {
		pq.offer(A[i]);
	}
	int num = -1;
	while (k > 0) {
		num = pq.poll();
		k--;
	}
	return num;
}

Method 6 - Use Min Heap

This method is mainly an optimization of method 1. Instead of using temp[] array, use Min Heap.

  1. Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
  2. For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH. (The step 2 is O((n-k)*logk))       a) If the element is greater than the root then make it root and call heapify for MH       b) Else ignore it.
  3. Finally, MH has k largest elements and root of the MH is the kth largest element. Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)

Code:

public String kthLargestNumber(int[] nums, int k) {
	PriorityQueue<String> minHeap = new PriorityQueue<>();
	for (int num : nums) {
		minHeap.offer(num);
		if (minHeap.size() > k) {
			minHeap.poll(); // pop the minimum value in the heap
		}
	}
	return minHeap.poll();
}

Time complexity - O (N + (N-K+1) * log (n-k+1))

Method 7 - Use Order Statistics OR QuickSelect OR Randomized Selection 🏆

If you want a true O(n) algorithm, as opposed to O(kn) or something like that, then you should use quickselect (it’s basically quicksort where you throw out the partition that you’re not interested in). This is called finding the k-th order statistics. More details can be found here:

Kth Largest Element Using Randomized Selection

Time complexity - O(n)

Method 8 - Blum Floyd Pratt Rivest Tarjan Algorithm

Blum Floyd Pratt Rivest Tarjan Algorithm

Time Complexity - O(n)