Return the kth largest element of nums — that is, the element that would sit at index n - k if the array were sorted ascending.
- This is the kth largest value by position, not the kth distinct value: in
[3,2,3,1,2,4,5,5,6] the 4th largest is 4 - Do not sort the whole array. Use quickselect: partition, then recurse into the one side that can contain the answer — average O(n)
- Choose the pivot deterministically (median-of-three of the low, middle and high elements) so the result never depends on randomness
- The input array must not be modified — partition a copy