Quickselect and Top-K

Opening scenario

Kth Largest Element in an Array (LC 215). Given an unsorted nums and k, return the k-th largest element (k-th in sorted order, not the k-th distinct). nums=[3,2,1,5,6,4], k=2 → 5. The interviewer will press: "Can you beat O(n log n)? Can you do it without sorting? What if the data is a stream?"

LC numbers identify LeetCode problems.

Assume nums is nonempty and 1 <= k <= len(nums). Sorting is a useful baseline: what ordering information could you omit if you only need the element at one rank?

Question progression

Q1 — Why is sorting the wrong default here?

Question: The obvious solution sorts and indexes nums[-k] — O(n log n). What is that doing that you don't need?

Reasoning: Sorting fully orders all n elements, but you only need to know one element's final position — the k-th. You're paying to…