k'th Largest Element

In this video we investigate the "Quickselect" algorithm for finding the k'th largest (or smallest) element in an array. We also look at the heap based approach to this problem.

Table of Contents
Enroll in our 5-day mini coding interview class

Code Sample

/*
Kth Largest Element in an Array - LeetCode: https://leetcode.com/problems/kth-largest-element-in-an-array/
This optimal solution has the same fundamental reasoning that QuickSort uses. (the partitioning subroutine)
Check out that QuickSort video here: https://www.youtube.com/watch?v=uXBnyYuwPe8
This code passes all Leetcode test cases as of April 18 2019
Runtime: 1 ms, faster than 99.86% of Java online submissions for Kth Largest Element in an Array
The video to explain this code is here: https://www.youtube.com/watch?v=hGK_5n81drs
*/
/*
We make the assumption k is between 1 and n (where n is the length of the array)
The 1st largest element is the largest element.
The n'th largest element is the smallest element.
*/
public int findKthLargest(int[] arr, int k) {
/*
Keep track of the 'left' and 'right' space in which the
k'th largest element can possibly be, we will use these bounds
to know what section to actually partition around a choosen pivot
*/
int n = arr.length;
int left = 0;
int right = n - 1;
// A Random object we will use later repeatedly to choose random pivots
Random rand = new Random(0);
// While the bounds stay valid continue doing directed partitioning
while (left <= right) {
int choosenPivotIndex = rand.nextInt(right - left + 1) + left; // Pick a random pivot. Bounds are [left, right].
/*
Execute the actual partitioning and get back the final positition
of the pivot we choose after partitioning is over
*/
int finalIndexOfChoosenPivot = partition(arr, left, right, choosenPivotIndex);
// What does the 'finalIndexOfChoosenPivot' tell us?
if (finalIndexOfChoosenPivot == n - k) {
/*
Found. The pivot is index on index n - k. This is literally its final position if
the array we were given had been sorted. See how we saved work? We don't
need to sort the whole array
*/
return arr[finalIndexOfChoosenPivot];
} else if (finalIndexOfChoosenPivot > n - k) {
/*
k'th largest must be in the left partition. We "overshot" and need to go left
(and we do this by narrowing the right bound)
*/
right = finalIndexOfChoosenPivot - 1;
} else {
/*
finalIndexOfChoosenPivot < n - k
k'th largest must be in the right partition. We "undershot" and need to go right
(and we do this by narrowing the left bound)
*/
left = finalIndexOfChoosenPivot + 1;
}
}
return -1; // this will never be reached, necessary to compile
}
/*
So this subroutine is exactly what we do in QuickSort...partition around the value
that the 'pivotIndex' holds
The result is a "sandwich" at the end.
[ items < than the pivot ... pivotItem ... items > than the pivot]
*/
private int partition(int[] arr, int left, int right, int pivotIndex) {
// Grab the value at the pivot index we passed in
int pivotValue = arr[pivotIndex];
/*
Remember how partitioning works? We need to keep track of where
we last placed an item in the section of items "less than the
pivot"
We keep track of the tail index of this section. We will
need this later
*/
int lesserItemsTailIndex = left;
/*
Move the item at the 'pivotIndex' OUT OF THE WAY. We are about to
bulldoze through the partitioning space and we don't want it in
the way
*/
swap(arr, pivotIndex, right);
/*
Iterate from the left bound to 1 index right before the right bound
(where the choosen pivot value is now sitting in saftey)
*/
for (int i = left; i < right; i++) {
/*
If this item is less than the 'pivotValue' then we need to move
this item to the section of items "less than the pivot"
'lesserItemsTailIndex' keeps track of where we need to swap into
next...after doing the swap we advance it...you see how this is
coming together?
*/
if (arr[i] < pivotValue) {
swap(arr, i, lesserItemsTailIndex);
lesserItemsTailIndex++;
}
}
/*
Ok...partitioning is done. Swap the pivot item BACK into the space we just
partitioned at the 'lesserItemsTailIndex'...that's where the pivot item
belongs
In the middle of the "sandwich".
*/
swap(arr, right, lesserItemsTailIndex);
/*
Return the index of where we just put the pivot so that the caller knows its
final resting place (so that the caller can make the decisions it needs)
*/
return lesserItemsTailIndex;
}
private void swap(int[] arr, int first, int second) {
int temp = arr[first];
arr[first] = arr[second];
arr[second] = temp;
}