AI solution for JavaScript Coding Question on BFE.dev
45. find the K-th largest element in an unsorted array

One approach to find the K-th largest element in an unsorted array is by using Quick Select algorithm. This algorithm is a variation of Quick Sort algorithm and has an average time complexity of O(n).

The idea behind Quick Select is to partition the array using a pivot element and then recursively partition the sub-arrays based on the pivot until the K-th largest element is found.

Here is an implementation in JavaScript:

function quickSelect(arr, k) {
  if (arr.length === 1) return arr[0];
  
  // select a random pivot
  const pivotIndex = Math.floor(Math.random() * arr.length);
  const pivot = arr[pivotIndex];
  
  // partition the array based on pivot
  let left = [];
  let right = [];
  let equal = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] > pivot) {
      right.push(arr[i]);
    } else {
      equal.push(arr[i]);
    }
  }
  
  if (k <= right.length) {
    // the K-th largest element is in the right subarray
    return quickSelect(right, k);
  } else if (k > right.length + equal.length) {
    // the K-th largest element is in the left subarray
    return quickSelect(left, k - right.length - equal.length);
  } else {
    // the pivot is the K-th largest element
    return pivot;
  }
}

The quickSelect function takes an array and an integer k as inputs, and returns the K-th largest element of the array. It first selects a random pivot element from the array, and partition the array into three sub-arrays: elements smaller than the pivot, elements larger than the pivot, and elements equal to the pivot.

If the size of the right sub-array is greater than or equal to k, the K-th largest element is in the right sub-array, so we recursively call quickSelect on the right sub-array.

If the size of the right sub-array plus the size of the equal sub-array is less than k, the K-th largest element is in the left sub-array, so we recursively call quickSelect on the left sub-array, adjusting the K-th largest element accordingly.

Otherwise, the pivot is exactly the K-th largest element, so we return the pivot.

This algorithm has an average time complexity of O(n), but in worst case scenario (if the selected pivot is always the smallest or the largest element of the array) it might have a time complexity of O(n^2). However, the worst-case scenario is very unlikely when the pivot is selected randomly.