Quickselect — kth largest

Medium TimeO(n) average SpaceO(log n) stack

Given an unsorted array arr and a number k, return the kth largest value — for [3, 2, 1, 5, 6, 4] and k = 2 that is 5. k counts from 1, so k = 1 asks for the largest; duplicates count as separate positions, and k is never larger than the array.

Examples

Example 1

Input
arr = [3, 2, 1, 5, 6, 4]k = 2
Output
5
6 is the largest and 5 is the next, so the 2nd largest is 5.

Example 2

Input
arr = [3, 2, 1, 5, 6, 4]k = 1
Output
6
k = 1 asks for the largest value in the array, which is 6.

The Code

function quickselect(arr, k) {
  const target = arr.length - k;
  function select(low, high) {
    const pivot = arr[high];
    let store = low;
    for (let i = low; i < high; i++) {
      if (arr[i] < pivot) {
        const temp = arr[i];
        arr[i] = arr[store];
        arr[store] = temp;
        store++;
      }
    }
    const temp = arr[high];
    arr[high] = arr[store];
    arr[store] = temp;
    if (store === target) return arr[store];
    if (store < target) return select(store + 1, high);
    return select(low, store - 1);
  }
  return select(0, arr.length - 1);
}
quickselect([3, 2, 1, 5, 6, 4], 2);
Done
Step through quickselect([3, 2, 1, 5, 6, 4], 2) call by call

More like this

All sorting examples (8) →