Coding Challenge Practice - Question 97

The task is to find the k-th largest element in an unsorted array which might contain duplicates.

The boilerplate code

function findKThLargest(arr, k) {
  // your code here
}

The k-th largest element is the element that would appear in position K, if the array was arranged in descending order. The k-th largest element is the same as the (n-k)th smallest element.

const target = arr.length - k;

Pick the last element as the pivot. All elements smaller than the pivot will be on the left, and elements bigger than the pivot will be on the right.

function partition(left, right) {
  const pivot = arr[right];
  let i = left;

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }

  [arr[i], arr[right]] = [arr[right], arr[i]];
  return i;
}

If the index of the pivot is equal to the target, then that's the k-th largest element.

const pivotIndex = partition(left, right);

if(pivotIndex === target) return arr[pivotIndex];

If the pivot index is less than the target, search the right side

if (pivotIndex < target) return quickSelect(pivotIndex + 1, right);

If the pivot index is greater than the pivot, search the left side

 return quickSelect(left, pivotIndex - 1);

This way, only one side is explored which is faster than a full sort. The final code

function findKThLargest(arr, k) {
  // your code here
  if(k < 1 || k > arr.length) return undefined;

  const target = arr.length - k;

  function partition(left, right) {
    const pivot = arr[right];
    let i = left;

    for(let j = left; j < right; j++) {
      if(arr[j] <= pivot) {
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
      }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
  }

  function quickSelect(left, right) {
    const pivotIndex = partition(left, right);

    if(pivotIndex === target) return arr[pivotIndex];
    if(pivotIndex < target) return quickSelect(pivotIndex + 1, right);
    return quickSelect(left, pivotIndex - 1);
  }

  return quickSelect(0, arr.length - 1);
}

That's all folks!