Sorting & Selection
Quickselect
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
kth largestkth smallesttop kmedianrankselection
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Do you need the kth item, not a fully sorted array?
- Is average O(n) better than O(n log n)?
- Can partitioning discard half the search space?
Classic problem
Kth Largest Element in an Array (LeetCode 215) — partition around a pivot and recurse
only into the side holding the target rank. The kth largest is the (n - k)th smallest.
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5 — the 2nd largest element, found without fully sorting the array.
Common pitfalls
Mixing kth-largest with zero-based kth-smallest indexes.
Worst-case O(n^2) without randomized or robust pivot choice.