find the kth largest element in an array in javascript

To find the kth largest element in an array, one approach is to sort the array in descending order and return the kth element. However, this approach has a time complexity of O(n log n), where n is the length of the array, which can be inefficient for large arrays. A more efficient approach is the quickselect algorithm, which has an average time complexity of O(n).

Here is an implementation of the quickselect algorithm in JavaScript:


index.tsx
function quickselect(arr, k, left = 0, right = arr.length - 1) {
  if (left === right) { // base case
    return arr[left];
  }

  // partition the array
  let pivotIndex = Math.floor((left + right) / 2);
  pivotIndex = partition(arr, left, right, pivotIndex);

  // the pivot is in its final sorted position
  if (k === pivotIndex) {
    return arr[k];
  } else if (k < pivotIndex) {
    // recurse on the left side
    return quickselect(arr, k, left, pivotIndex - 1);
  } else {
    // recurse on the right side
    return quickselect(arr, k, pivotIndex + 1, right);
  }
}

function partition(arr, left, right, pivotIndex) {
  const pivotValue = arr[pivotIndex];
  let i = left; // index of smaller element

  // move the pivot to the right
  swap(arr, pivotIndex, right);

  for (let j = left; j < right; j++) {
    if (arr[j] > pivotValue) {
      swap(arr, i, j); // swap elements
      i++;
    }
  }

  // move the pivot to its final sorted position
  swap(arr, i, right);

  return i;
}

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
1085 chars
47 lines

The quickselect function takes an array arr, an integer k, the left and right indices of the subarray to quickselect (defaulting to the entire array), and returns the kth largest element in arr. The partition function does the partitioning work, and the swap function is a helper function for swapping elements in an array.

To use the quickselect function, simply call it with the array and k argument:


index.tsx
const arr = [5, 3, 9, 1, 7];
const k = 2;

const kthLargest = quickselect(arr, k - 1); // since arrays are zero-indexed, we pass k-1 instead of k
console.log(kthLargest); // Output: 5
184 chars
6 lines

similar javascript code snippets

find the kth largest element in an array in javascript

sort an array in javascript

find the kth longest word in a string in javascript

find the kth smallest element in an array in javascript

sort by property in javascript

find the kth least frequent element in an array in javascript

sort an array of arrays by the name field in javascript

sort an array of objects in javascript

find index of an object in an array in javascript

remove an object from an array in javascript

related categories