Find the kth largest element in an unsorted array using Quickselect?

public int FindKthLargest(int[] nums, int k) {

return QuickSelect(nums, 0, nums.Length - 1, nums.Length - k);

private int QuickSelect(int[] nums, int left, int right, int

kSmallest) {

if (left == right) return nums[left];

int pivotIndex = Partition(nums, left, right);

if (kSmallest == pivotIndex)

return nums[kSmallest];

else if (kSmallest < pivotIndex)

return QuickSelect(nums, left, pivotIndex - 1, kSmallest);

else

return QuickSelect(nums, pivotIndex + 1, right, kSmallest);

private int Partition(int[] nums, int left, int right) {

int pivot = nums[right];

int i = left;

for (int j = left; j < right; j++) {

if (nums[j] <= pivot) {

Swap(nums, i, j);

i++;

Swap(nums, i, right);

return i;

private void Swap(int[] nums, int i, int j) {

int temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

Follow on:

Explanation:

Quickselect partitions the array like Quicksort and recursively searches for the kth smallest

element. Here, nums.Length - k gives the kth largest.