<pre class="shiki github-dark shaku"><code>/** * @param {number[]} arr * @param {number} k */function findKThLargest(arr, k) { return partition(0, arr.length - 1, arr, arr.length - k);}// 1. pick lo as the pivot// 2. start i from lo and start j from hi, while i doesn't move pass j.// 3. move i forward until it finds an element bigger than the pivot element// 4. move j backwards until it finds an element smaller than or equal the pivot element, a complete opposite from step 3.// 5. if i &lt; j, swap i-th and j-th element// 6. else we're outside of the while loop, swap pivot with j to insert pivot into its sorted position.// 7. check if the pivot element is k from the end, aka = (arr.length - k), if it is, we found the k-th largest element, return// 8. else if j is smaller than k from the end, that means the element we're looking for is on the right side of j, partition again between (j+1, hi)// 9. Else partition between (lo, j-1)function partition(lo, hi, arr, k) { let pivot = arr[lo]; let i = lo; let j = hi; while (i &lt;= j) { if (arr[i] &lt;= pivot) { i++; } if (arr[j] &gt; pivot) { j--; } if (i &lt; j) { [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[j], arr[lo]] = [arr[lo], arr[j]]; if (j === k) { return arr[j]; } else if (j &lt; k) { return partition(j+1, hi, arr, k); } return partition(lo, j-1, arr, k);}</code></pre>

Quick select with robust explanation. But missing randomized pivoting for optimal O(n)

You are given an unsorted array of numbers, which might have duplicates, find the K-th largest element. The naive approach would be sort it first, but…