Kth Largest Element in an Array

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

 

Constraints:

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    let l = 0;
    let r = nums.length - 1;
    k = r - k + 1; // convert kth largest to kth smallest

    // quickselect
    while (l <= r) {
        let pivotIndex = partition(nums, l, r);
        if (pivotIndex > k) { // kth before pivotIndex
            r = pivotIndex - 1;
        } else if (pivotIndex < k) { // kth after pivotIndex
            l = pivotIndex + 1;
        } else { // kth is pivotIndex
            return nums[k];
        }
    }
};

// partition all values < nums[r] to left and > nums[r] to right
var partition = function(nums, l, r) {
    const pivot = nums[r];
    for (let i = l; i < r; i++) {
        if (nums[i] < pivot) {
            [nums[i], nums[l]] = [nums[l], nums[i]];
            l++
        }
    }
    [nums[l], nums[r]] = [nums[r], nums[l]]; // put pivot at correct index
    return l; // index of pivot
};

Use quickselect to find the kth largest value.