1. Introduction
In this article, we’ll present various solutions for finding the kth largest element in a sequence of unique numbers. We’ll use an array of integers for our examples.
We’ll also talk about each algorithm’s average and worst-case time complexity.
2. Solutions
Now let’s explore a few possible solutions — one using a plain sort, and two using the Quick Select algorithm derived from Quick Sort.
2.1. Sorting
When we think about the problem, perhaps the most obvious solution that comes to mind is to sort the array.
Let’s define the steps required:
- Sort the array in ascending order
- As the last element of the array would be the largest element, the kth largest element would be at xth index, where x = length(array) – k
As we can see, the solution is straightforward but requires sorting of the entire array. Hence, the time complexity will be O(n*logn):
public int findKthLargestBySorting(Integer[] arr, int k) {
Arrays.sort(arr);
int targetIndex = arr.length - k;
return arr[targetIndex];
}
An alternative approach is to sort the array in descending order and simply return the element on *(k-1)*th index:
public int findKthLargestBySortingDesc(Integer[] arr, int k) {
Arrays.sort(arr, Collections.reverseOrder());
return arr[k-1];
}
2.2. QuickSelect
This can be considered an optimization of the previous approach. In this, we pick the QuickSort for sorting. Analyzing the problem statement, we realize that *we don’t actually need to sort the entire array — we only need to rearrange its contents so that the kth element of the array is the kth largest or smallest.*
In QuickSort, we pick a pivot element and move it to its correct position. We also partition the array around it. *In QuickSelect, the idea is to stop at the point where the pivot itself is the kth largest element.*
We can optimize the algorithm further if we don’t recur for both left and right sides of the pivot. We only need to recur for one of them according to the position of the pivot.
Let’s look at the basic ideas of the QuickSelect algorithm:
- Pick a pivot element and partition the array accordingly
- Pick the rightmost element as pivot
- Reshuffle the array such that pivot element is placed at its rightful place — all elements less than the pivot would be at lower indexes, and elements greater than the pivot would be placed at higher indexes than the pivot
- If pivot is placed at the kth element in the array, exit the process, as pivot is the kth largest element
- If pivot position is greater than k, then continue the process with the left subarray, otherwise, recur the process with right subarray
We can write generic logic which can be used to find the kth smallest element as well. We’ll define a method findKthElementByQuickSelect() which will return the kth element in the sorted array.
If we sort the array in ascending order, the kth element of an array will be the kth smallest element. To find the kth largest element, we can pass k= length(Array) – k.
Let’s implement this solution:
public int
findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) {
if (k >= 0 && k <= right - left + 1) {
int pos = partition(arr, left, right);
if (pos - left == k) {
return arr[pos];
}
if (pos - left > k) {
return findKthElementByQuickSelect(arr, left, pos - 1, k);
}
return findKthElementByQuickSelect(arr, pos + 1,
right, k - pos + left - 1);
}
return 0;
}
Now let’s implement the partition method, which picks the rightmost element as a pivot, puts it at the appropriate index, and partitions the array in such a way that elements at lower indexes should be less than the pivot element.
Similarly, elements at higher indexes will be greater than the pivot element:
public int partition(Integer[] arr, int left, int right) {
int pivot = arr[right];
Integer[] leftArr;
Integer[] rightArr;
leftArr = IntStream.range(left, right)
.filter(i -> arr[i] < pivot)
.map(i -> arr[i])
.boxed()
.toArray(Integer[]::new);
rightArr = IntStream.range(left, right)
.filter(i -> arr[i] > pivot)
.map(i -> arr[i])
.boxed()
.toArray(Integer[]::new);
int leftArraySize = leftArr.length;
System.arraycopy(leftArr, 0, arr, left, leftArraySize);
arr[leftArraySize+left] = pivot;
System.arraycopy(rightArr, 0, arr, left + leftArraySize + 1,
rightArr.length);
return left + leftArraySize;
}
There’s a simpler, iterative approach to achieve the partitioning:
public int partitionIterative(Integer[] arr, int left, int right) {
int pivot = arr[right], i = left;
for (int j = left; j <= right - 1; j++) {
if (arr[j] <= pivot) {
swap(arr, i, j);
i++;
}
}
swap(arr, i, right);
return i;
}
public void swap(Integer[] arr, int n1, int n2) {
int temp = arr[n2];
arr[n2] = arr[n1];
arr[n1] = temp;
}
This solution works in O(n) time on average. However, in the worst case, the time complexity will be O(n^2).
2.3. QuickSelect With Randomized Partition
This approach is a slight modification of the previous approach. If the array is almost/fully sorted and if we pick the rightmost element as a pivot, the partition of left and right subarrays will be highly uneven.
This method suggests picking the initial pivot element in a random manner. We don’t need to change the partitioning logic though.
Instead of calling partition, we call the randomPartition method, which picks a random element and swaps it with the rightmost element before finally invoking the partition method.
Let’s implement the randomPartition method:
public int randomPartition(Integer arr[], int left, int right) {
int n = right - left + 1;
int pivot = (int) (Math.random()) * n;
swap(arr, left + pivot, right);
return partition(arr, left, right);
}
This solution works better than the previous case in most cases.
The expected time complexity of randomized QuickSelect is O(n).
However, the worst time complexity still remains O(n^2).
3. Conclusion
In this article, we discussed different solutions to find the kth largest (or smallest) element in an array of unique numbers. The simplest solution is to sort the array and return the kth element. This solution has a time complexity of O(n*logn).
We also discussed two variations of Quick Select. This algorithm isn’t straightforward but it has a time complexity of O(n) in average cases.
As always, the complete code for the algorithm can be found over on GitHub.