# 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.