Coding Challenge Practice - Question 97

Source: Dev.to

Problem Description

The task is to find the k‑th largest element in an unsorted array that may contain duplicates.

The k‑th largest element is the element that would appear in position k if the array were sorted in descending order. It is equivalent to the ((n - k))-th smallest element, where (n) is the length of the array.

const target = arr.length - k;

Solution Overview

A quick‑select algorithm can locate the desired element without fully sorting the array.

1. Choose a pivot – pick the last element of the current sub‑array.
2. Partition – move all elements ≤ pivot to the left and the rest to the right.
3. Compare the pivot index with target:
   • If they are equal, the pivot is the k‑th largest element.
   • If the pivot index is less than target, recurse on the right side.
   • If the pivot index is greater than target, recurse on the left side.

Only one side of the partition is explored at each step, giving average‑case linear time (O(n)).

Partition Function

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

  for (let j = left; j  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!