Kth Largest Element in an unsorted Array

Note that it is the k^th largest element in the sorted order, not the k^th distinct element.

Example 1

Input: nums = [3, 2, 1, 5, 6, 4] and K = 2 Output: 5 Explanation : after sorting above array, it will become [1, 2, 3, 4 , 5 , 6]. So 2^nd largest element is 5.

Example 2

Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] and K = 4 Output: 4 Explanation: after sorting above array, it will become [1, 2, 2, 3, 3, 4 , 5, 5, 6]. So 4^th largest element is 4.

Note: You can assume k is a valid number, that is 1 <= k <= array.length

Solution 1 - Using sorting
Solution 2 - Using Min Heap
Solution 3 - Using QuickSelect algorithm

using sorting

In this solution we are going sort the array first, then simply get array.lenth - k^th element (i.e. taking K^th element from bottom after sorting in incremental order).

public int findKthLargestUsingSorting(int[] input, int k) { Arrays.sort(input); return input[input.length-k]; }

Complexity Analysis:

Above code runs in O(n log n) time complexity where n is the size of the array. Sorting of the input array Arrays.sort(input) takes O(n log n) time, once the array is sorted then fetching an element using its index takes constant time. Space complexity is constant O(1) as we are not using additional space.

This solution is definitely a overkill to sort entire array for getting just one number.

using Min Heap

In this solution we are going use an intermediate data structure, Min Heap (PriorityQueue in Java) to store array elements.
Min Heap works such a way that, it always keeps the min element at the top of Queue. So, what we are going to do is whenever Min Heap is filled with K elements, then remove the top element when a new element is inserted to ensure that Min Hep has only K elements at any given point of time and K^th largest stays at top.

As you loop through elements in the array, add them to PriorityQueue using PriorityQueue.add(element)
Then, check if the PriorityQueue already filled with K+1 elements, then remove the top element using PriorityQueue.poll(), leaving exactly K elements in the Heap.

Once we visited all elements in array, simply return the top element using , which is nothing but K^th largest element.

public int findKthLargestUsingMinHeap(int[] input, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); for(int num : input) { minHeap.add(num); if(minHeap.size() > k) { // check when min heap has K+1 th element minHeap.poll(); // remove the top element to ensure it has only K elements } } return minHeap.peek(); // finally return top element, which is nothing but Kth largest }

Complexity Analysis:

Above code runs in O( n log k) time complexity where n is the size of the array and k is the size of Heap.

Min Heap runs a procedure called heapify() to make sure that min element stays at top whenever a new element is added or removed, and this runs in O (log k) time as we are only keeping at most K elements at any given time. This loop is repeated for all elements in the input array, hence O (n log (k)). Space complexity is O(k) as we are using an intermediate data structure Min Heap with size k.

This is better than previous solution if K is reasonably less than N.

using Quickselect algorithm

The main idea behind this solution is to use Quickselect algorithm, it uses the same technique as Quicksort algorithm and find K^th largest element.

K^th largest element is nothing but K^th index from right when the array is sorted, so we will refer K as (array.length-K)^th indexed element below.

Similar to Quicksort algorithm, we will choose an element from the array as pivot and partition the array such that all the elements smaller than pivot are aligned to left and greater than pivot are aligned to right side. This is achieved using method in below code.
Once the array is split with pivot element in the middle, resultant array looks like below diagram. It is also true that the pivot element is correctly positioned to its place if the array is fully sorted.

Pivot partitioned array into two parts with lesser elements on left and greater elements on right side

Now, we can draw three conclusions from above.

If pivot's index is K, then we have found our answer.
If pivot's index is less than K, then our answers in on left side of the array. So, repeat above steps on pivot's left side sub array [left,.....,pivot-1].
If pivot's index is greater than K, then our answers in on right side of the array. So, repeat above steps on pivot's right side sub array [pivot+1,.....,right].

Let's understand this with an example

Input Array : [3, 2, 1, 9, 8, 5, 6] and K = 2.

Since we have to find 2^nd largest element and the input array size is 7, so 2^nd largest element is nothing but 5^th indexed element after array is sorted.

Step 1: We are going to choose right most element as pivot, that is 6.

You can select any random element as pivot, but there are two popular partition schemes to choose a pivot, Lomuto partition and Hoare partition, in this solution we choose Lomuto partition, so we are going to choose right most element as pivot

Step 2: Using 6 as pivot element, move all elements smaller than 6 to left side and greater than 6 to right side of array using compare and swap technique, so the resultant array looks like this [3,2,1,5, 6 ,9,8].
If you take a closer look at the resultant array after step 2, pivot element is positioned at index 4, which is the correct position when the array is fully sorted.

Step 3: Now, draw one of below conclusions.

Is the pivot's new position is K ? if YES then we have found our answer, but pivot's position is 4, but we are looking for 5^th indexed element from sorted array.
Now, we know for sure our answer will be between index 4 and 6. So, repeat above steps for this sub array [4,...,6] and at one point, pivot's position will be equal to K.

After step 3, we can eliminate left partitioned array and just continue above three steps using this new sub array with indexes [pivot_index+1,.....,right].

Complexity Analysis:

QuickSelect algorithm runs in O(n) time complexity in average case where n is the size of the array and O(n²) in the worst case scenario (If numbers are already sorted and pivot selection is bad).
This procedure is an in-place algorithm, so it takes O(1) constant space.

public int quickSelect(int[] nums, int k) { //we are going to find nums.length - k th bigger element from left in the sorting order k = nums.length -k; return select(nums, 0, nums.length-1, k); } public int select(int[] nums, int left, int right, int k) { if(left==right) { // in case nums contains only on element - will return that return nums[left]; } int storeIndex = partition(nums,left,right); if(k == storeIndex) { return nums[k]; } else if (k<storeIndex) { return select(nums, left, storeIndex-1, k); } else { return select(nums, storeIndex+1, right, k); } } public int partition(int[] nums, int left, int right) { int pivotValue = nums[right]; int storeIndex = left; for(int i=left; i<right; i++) { if(nums[i]<pivotValue) { swap(nums, i, storeIndex); storeIndex++; } } swap(nums,right,storeIndex); // move pivot to its final place return storeIndex; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

Partition algorithm illustration:

For the illustration purpose, let's take input array as [3, 2, 1, 9, 8, 5, 6] and K = 2. So K^th largest element is nothing but array.length - K^th element when the array is sorted, that is 5^th indexed element.

Input Array : Input array [3, 2, 1, 9, 8, 5, 6]

Step 1 is to pick a pivot element, we are choosing right most element, that is pivot = array[right] = 6.

Pivot element selected

Step 2 initialize two variables storeIndex and leftIndex with left index, that is storeIndex = 0, leftIndex = 0 and loop through from left to right-1 and start comparing with pivot.

If the element is less than pivot then swap storeIndex element with leftIndex element that is currently at, and increment storeIndex and leftIndex.
If the element is greater than or equal to pivot then don't swap elements, increment leftIndex and continue with next element.

storeIndex=0 initialization

In 1^st iteration, check array[leftIndex] < pivot , that is3 < 6? this is true, so swap array[leftIndex] and array[storeIndex], since left index and storeIndex are same, after swapping resultant array will be same [3, 2, 1, 9, 8, 5, 6]. Now increment storeIndex, so storeIndex = 1

First Iteration of checking leftIndex value is less than Pivot or not

After first iteration updating storeIndex

In 2^nd iteration, check array[leftIndex] < pivot , that is2 < 6? this is true, so swap array[leftIndex] and array[storeIndex]. After swap resultant array will be same as input array and storeIndex will be incremented to 2.

second Iteration of checking leftIndex value is less than Pivot or not

After second iteration updating storeIndex

In 3^rd iteration also, array will be same as input array after swapping and storeIndex will be incremented to 3.

third Iteration of checking leftIndex value is less than Pivot or not

After third iteration updating storeIndex

In 4^th iteration, check array[leftIndex] < pivot , that is9 < 6? this is false, so we will not swap elements and storeIndex is not touched.

fourth Iteration of checking leftIndex value is less than Pivot or not

After fourth iteration updating storeIndex

In 5^th iteration, check array[leftIndex] < pivot , that is8 < 6? this is false, so we will not swap elements and storeIndex is not touched.

fifth Iteration of checking leftIndex value is less than Pivot or not

After fifth iteration updating storeIndex

In 6^th iteration, check array[leftIndex] < pivot , that is5 < 6? this is true, so swap array[leftIndex] and array[storeIndex]. After swap resultant array will look like [3, 2, 1, 5, 8, 9, 6] and storeIndex will be incremented to 4.

fifth Iteration of checking leftIndex value is less than Pivot or not

After fifth iteration updating storeIndex

We have come to end of loop, now swap storeIndex and right index (pivot element) to complete the partitioning and the array now looks like this [3, 2, 1, 5, 6, 9, 8].

swap storeIndex and pivot

pivot is back tp its position

Now, check where the pivot element is positioned at (storeIndex) and compare this with K, pivot is now at 4^th index, but we are looking for 5^th indexed element after sorting.
At this step we know for sure our answer is on right partition of the array, so we will continue all the steps described above with leftIndex as 5 and rightIndex as 6.

Once the array goes through method with left and right boundaries as [9,8], it will return answer as 8. That is the 2^nd largest element after array is sorted.

Above examples source code can be found at GitHub link for Java code and JUnit tests can be found at GitHub link for Unit tests code