Kth largest element in an Array

Kth largest element in an array can be determined using the “Quickselect Algorithm”.

Average performance O(n)
Worst-case performance O(n^2)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
  var n = nums.length;
  // Kth largest element is the n - k + 1 smallest element.
  // n - k for index.
  return findRank(nums, n - k, 0, n - 1);
};

var findRank = function(nums, r, left, right) {
  if (left === right)
    return nums[left];
  var pivot = Math.floor(Math.random() * (right - left + 1)) + left;
  var leftEnd = getPivot(pivot, nums, left, right);
  if (leftEnd === r)
    return nums[leftEnd];
  else if (r < leftEnd) {
    return findRank(nums, r, left, leftEnd - 1);
  }
  return findRank(nums, r, leftEnd + 1, right);
};

var getPivot = function(pivot, nums, left, right) {
  swap(nums, pivot, right);
  var index = left;
   for (let i = left; i <= right; i++) {
       if (nums[i] < nums[right]) {
           swap(nums, i, index++);
       }
   }
   swap(nums, index, right);
   return index;
}

var swap = function(arr, x, y) {
    var temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

console.log(findKthLargest([7,6,5,1,2,3,4], 5));

Output

Demo

Related