Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The kth largest is the (n−k)th smallest, so it sits at 0-indexed position n−k in ascending order. Quickselect partitions around a pivot (Hoare or Lomuto) and recurses into only the side holding index n−k — O(n) average because the work halves each step, O(n²) worst case fixed by a random pivot. The size-k min-heap is the O(n log k) baseline whose top is always the kth largest.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you map kth largest to index n − k cleanly, implement partition correctly (Hoare or Lomuto), and articulate why one-sided recursion is O(n) average while honestly stating the O(n²) worst case.
Where candidates slip
Using the kth-smallest index k − 1 instead of n − k, recursing into both partition halves, or asserting O(n) worst case without a random pivot.
How to stand out
State the index mapping out loud, choose Lomuto or Hoare deliberately and say why, add the random-pivot guard unprompted, and offer the size-k min-heap as the streaming-safe alternative with its O(n log k) bound.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewNeed the kth LARGESTWorst-case guarantee or streaming?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Min-Heap of Size k — Baseline
1Hint 1Explore hintHide hint
If you keep only the k largest elements seen so far, the smallest among them is the kth largest. What structure exposes the current minimum in O(1) and removes it in O(log k)?
2Hint 2Explore hintHide hint
Use a min-heap capped at size k. Push each element; if the heap grows past k, pop the smallest. The heap always holds the k largest seen.
3Hint 3Explore hintHide hint
After processing every element, the heap's top (its minimum) is exactly the kth largest of the whole array.
A · Core idea
Reframe 'kth largest' as 'the smallest of the k largest'. If you hang onto only the k biggest elements you've seen, then the smallest of those k is the kth largest once every element has been processed.
Why a min-heap, not a max-heap. You want O(1) access to the smallest of your current k keepers, because that's the one most likely to be kicked out when a bigger element arrives. A min-heap puts that smallest on top. Push each new element; if the heap reaches k + 1, pop the top (the smallest) — it can't be among the k largest. After the full pass, the heap holds exactly the k largest and its top is the kth largest.
Why the size cap keeps it fast. Every heap operation costs O(log(size)), and size never exceeds k. So although you touch all n elements, each costs O(log k). When k is small relative to n, O(n log k) beats the O(n log n) of a full sort — and unlike quickselect it never degrades on bad input.
Why it suits streams. You only ever hold k elements, so data can arrive incrementally and memory stays at O(k). That makes the heap the default when the input is a stream or when space is tight. The cost is the log k factor on every element, which quickselect avoids on average at the price of mutating and needing the whole array up front.
Mirror of kth smallest. For kth smallest you'd use a max-heap of size k. The rule of thumb: pick the heap orientation opposite to what you're selecting, so the easiest-to-discard element sits at the top.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [3, 2, 1, 5, 6, 4], k = 2Array state
after 2
heap holds {2, 3}
5C · Code with teaching comments
Reference implementation previewpublic int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // natural order = min-heap for (int x : nums) { minHeap.offer(x); if (minHeap.size() > k) {Explore the full codeHide the full code
D · Why it works and complexityO(n log k) timeO(k) spaceOpen the invariant and proofExplore the proofHide the proof
This is the reusable 'keep the best k seen so far' engine — the same one behind Top K Frequent Elements, K Closest Points to Origin, and Kth Largest in a Stream. The only design decision is the comparator: a min-heap to track the largest, a max-heap to track the smallest.
ComplexityO(n log k) time, O(k) space — n pushes of O(log k) on a heap bounded by k, plus up to n pops of O(log k) → O(n log k) time. The heap holds at most k elements → O(k) space.
E · Edge cases and pitfalls3Using a max-heap by reflex — then the top is the largest, not the kth largest.Explore edge casesHide edge cases
Pitfalls
- Using a max-heap by reflex — then the top is the largest, not the kth largest.
- Forgetting the size cap — the heap grows to n, degrading to O(n log n).
- Returning poll() instead of peek() — pop mutates the heap and loses the answer.
Approach 2 of 2 · Optimal
Quickselect — Hoare/Lomuto Partition (Optimal)
1Hint 1Explore hintHide hint
Quicksort's partition fixes one pivot in its final sorted position p and splits the rest into < pivot and ≥ pivot. If p equals your target index n − k, that pivot is the answer.
2Hint 2Explore hintHide hint
If p < target, the answer is in the right part; if p > target, it's in the left. Recurse (or loop) into only that side — never both.
3Hint 3Explore hintHide hint
Map kth largest to target = n - k in ascending order. Average work n + n/2 + n/4 + … = 2n = O(n). Add a random pivot to dodge the O(n²) worst case.
A · Core idea
Quickselect is quicksort minus the half you don't need. Since you only want one position, you discard the side that can't contain it.
Index mapping first. The kth largest in ascending sorted order lives at position n − k: the largest (k = 1) is at n − 1, the smallest-of-the-top-k is further left. Compute target = n − k once — this is the entire difference from the kth-smallest version, which targets k − 1. Getting this mapping right (and not confusing it with k − 1) is the first thing to verify aloud.
The partition primitive — Lomuto. Pick a pivot (here nums[hi]). Sweep j from lo to hi−1 with a boundary i: each element strictly less than the pivot is swapped to the left of i, advancing i. Finally swap the pivot into slot i. Now nums[i] is in its final sorted position, smaller elements to its left, ≥ elements to its right. The returned p = i is the pivot's true rank.
Hoare's alternative. Hoare's scheme runs two pointers inward from both ends, swapping out-of-place pairs until they cross. It performs fewer swaps on average than Lomuto, but its returned split index doesn't land the pivot in its final position, so the recursion boundaries are subtler. Both are valid; Lomuto is easier to reason about under interview pressure, which is why the code below uses it. Mentioning that you know Hoare exists and trades fewer swaps for trickier bookkeeping is a strong signal.
The one-sided shortcut. Compare p to target. If p == target, return nums[p] — done. If p < target, the answer is strictly to the right: set lo = p + 1 and repeat on the right segment only. If p > target, set hi = p − 1. Recursing into a single side is exactly what turns quicksort's O(n log n) into quickselect's O(n) average — you throw away half the remaining work each step.
Average vs worst, and the fix. A balanced pivot halves the range, telescoping to 2n = O(n). But a pivot that is always the max or min — what a fixed last-element pivot does on sorted or reverse-sorted input — shrinks the range by one per step, giving O(n²). The standard guard is a random pivot: swap a uniformly random index into the pivot slot before partitioning, so no input ordering can force bad splits. For a hard worst-case guarantee, median-of-medians selects a provably good pivot in O(n), achieving O(n) worst case with a larger constant.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [3, 2, 1, 5, 6, 4], k = 2Array state
partition full
pivot 4 → p=3 < 4 → keep right [4..5]
5C · Code with teaching comments
D · Why it works and complexityO(n) average, O(n²) worst timeO(1) iterative spaceOpen the invariant and proofExplore the proofHide the proof
Kth largest and kth smallest are the same algorithm viewed from opposite ends — the only thing that changes is target = n − k versus target = k − 1. Internalize that reflection and you stop memorizing two solutions. More broadly, quickselect embodies 'compute only the order you were asked for': sorting answers every rank, selection answers one, so selection is cheaper.
ComplexityO(n) average, O(n²) worst time, O(1) iterative space — Each partition is O(size). An average (roughly balanced) pivot halves the range, so total work telescopes to n + n/2 + n/4 + … = 2n = O(n). Adversarial input that always selects an extreme pivot gives n + (n−1) + … = O(n²); a random pivot makes that effectively impossible. The iterative loop adds O(1) space.
E · Edge cases and pitfalls8nums = [1], k = 1 — target = 0; first partition returns p = 0 = target → returns 1.Explore edge casesHide edge cases
Edge cases handled
nums = [1], k = 1target = 0; first partition returns p = 0 = target → returns 1.nums = [2, 1], k = 2target = 0 (the minimum); quickselect drives lo/hi to index 0 → returns 1.nums = [7, 7, 7], k = 2All duplicates; every value is 7 so any partition yields 7 at the target index.nums = [1, 2, 3, 4, 5], k = 1 (sorted)Random pivot avoids the O(n²) blowup a fixed last-element pivot would suffer here.
Pitfalls
- Using target = k − 1 (kth smallest) instead of n − k — silently returns the wrong end.
- Recursing into both sides — that's quicksort, O(n log n), not quickselect.
- Claiming O(n) worst case — it's O(n²) without a random pivot on sorted input.
- Hoare partition: returning the wrong boundary index, so the recursion skips or repeats elements.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int findKthLargest(int[] nums, int k) { int lo = 0, hi = nums.length - 1, target = nums.length - k; Random rnd = new Random(); while (lo <= hi) { int p = partition(nums, lo, hi, rnd);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong target index
Kth largest sits at n − k in ascending order. Using k − 1 returns the kth smallest instead — the most common copy-paste bug when adapting the smallest version.
Explore the code comparisonHide the code comparison
Wrong target index
Kth largest sits at n − k in ascending order. Using k − 1 returns the kth smallest instead — the most common copy-paste bug when adapting the smallest version.
Don't write this
int target = k - 1; // WRONG: that's the kth SMALLESTWrite this instead
int target = nums.length - k; // kth largest in ascending order2Recursing into both sides
Quickselect's O(n) average comes from discarding the side that can't hold the target. Recursing into both is quicksort — O(n log n).
Explore the code comparisonHide the code comparison
Recursing into both sides
Quickselect's O(n) average comes from discarding the side that can't hold the target. Recursing into both is quicksort — O(n log n).
Don't write this
p = self._partition(nums, lo, hi)
self.select(nums, lo, p - 1, target) # WRONG: recurses left
self.select(nums, p + 1, hi, target) # and rightWrite this instead
p = self._partition(nums, lo, hi)
if p == target:
return nums[p]
elif p < target:
lo = p + 1 # one side only
else:
hi = p - 13Fixed pivot on sorted input
Always choosing the last element as the pivot makes sorted or reverse-sorted input degrade to O(n²) — each partition peels off a single element.
Explore the code comparisonHide the code comparison
Fixed pivot on sorted input
Always choosing the last element as the pivot makes sorted or reverse-sorted input degrade to O(n²) — each partition peels off a single element.
Don't write this
int pivot = nums[hi]; // fixed pivot → O(n^2) on sorted inputWrite this instead
int r = lo + rnd.nextInt(hi - lo + 1);
swap(nums, r, hi); // randomize → expected O(n)
int pivot = nums[hi];Revise
Carry the pattern into the interview
Pattern to remember
Quickselect — partition, recurse into one side, target index n − k
Code pattern to memorize
target = n - k # 0-indexed position of kth LARGEST (ascending)
lo, hi = 0, n - 1
while lo <= hi:
p = partition(lo, hi) # Lomuto: < pivot left, pivot at p
if p == target: return nums[p]
elif p < target: lo = p + 1
else: hi = p - 1Rules to remember
- 1kth largest in ascending order = index
n − k. The mirror of kth smallest (indexk − 1). Mixing the two formulas is the classic bug. - 2Quickselect recurses into one side only — that's the O(n) average win. Recursing into both is quicksort, O(n log n).
- 3Lomuto uses one boundary pointer and is easy to get right; Hoare uses two pointers crossing inward — fewer swaps but trickier index returns. Either works; know which you're writing.
- 4Worst case O(n²) hits when the pivot is always extreme (sorted/reverse-sorted input). Randomize the pivot (swap a random index into the pivot slot) to make that vanishingly unlikely.
- 5The size-k min-heap baseline keeps the k largest seen; its top (the minimum of those k) is the kth largest. O(n log k) time, O(k) space, no worst-case blowup, and it streams.
Use this pattern when
- You need a single order statistic (kth largest, median) from an unsorted, mutable array
- Average-case O(n) matters and the input isn't adversarial
- In-place is fine — quickselect partitions and reorders the array
- For a streaming or memory-bounded variant, fall back to the size-k min-heap
Choose another pattern when
- You need the top-k elements sorted, not just the kth → heap or partial sort
- Worst-case O(n) is required on adversarial input → median-of-medians, or the heap
- Input must stay in original order and can't be copied → quickselect's swaps are out
- Repeated kth queries on static data → sort once, index in O(1)
Interview takeaway
Kth largest is kth smallest reflected across the array — target index n − k instead of k − 1. Quickselect reuses the partition primitive and discards half the work each step for O(n) average; the size-k min-heap is the safe O(n log k) fallback. Naming Hoare vs Lomuto and the random-pivot fix is what separates a memorized solution from understanding.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Quickselect (order statistics). Trigger whenever you need a single kth largest/smallest from an unsorted, mutable array and want O(n) average. Reuse quicksort's partition (Hoare or Lomuto) but recurse into one side only; target index n − k for largest, k − 1 for smallest. The size-k heap is the O(n log k) streaming-safe fallback; median-of-medians is the O(n) worst-case variant.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Kth Smallest Element in an ArrayComing soonSame partition; target index k − 1 instead of n − k.
- Kth Largest Element in a StreamComing soonMaintain a size-k min-heap across an online sequence of inserts.
- Top K Frequent ElementsComing soonQuickselect or a size-k heap over (value, frequency) pairs.
- K Closest Points to OriginComing soonQuickselect on squared distance, or a size-k max-heap.