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}
 */
const findKthLargest = function(nums, k) {
  const n = nums.length;
  return findRank(nums, n - k, 0, n - 1);
};

const findRank = (nums, r, left, right) => {
  if (left === right)
    return nums[left];
  const pivot = Math.floor(Math.random() * (right - left + 1)) + left;
  const 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);
};

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

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

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

Output

Demo

Related