Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Don't sort the whole array — you only need one order statistic. A size-k max-heap gives the kth smallest in O(n log k). Quickselect does better: partition around a pivot (the same partition merge sort/quicksort uses), and recurse into only the side that contains target index k−1. That's O(n) average because work halves each step (n + n/2 + n/4 + … = 2n); worst case O(n²), fixed in practice by a random pivot.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you avoid the lazy sort-and-index answer and reach for selection, can implement partition correctly, and understand why recursing into one side gives O(n) average while the heap gives O(n log k).
Where candidates slip
Off-by-one between k and k−1, recursing into both partition sides (turning quickselect back into quicksort), or claiming quickselect is O(n) worst case — it's O(n²) without a random pivot.
How to stand out
Offer the heap baseline first for its clean O(n log k) guarantee, then present quickselect for O(n) average, and proactively mention the random-pivot fix and the median-of-medians O(n) worst-case option.
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 smallestNeed the full sorted order too?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
Max-Heap of Size k — Baseline
1Hint 1Explore hintHide hint
If you keep only the k smallest elements seen so far, the largest among them is the kth smallest overall. What structure gives you the current largest in O(1) and removes it in O(log k)?
2Hint 2Explore hintHide hint
Use a max-heap capped at size k. Push each element; if the heap grows past k, pop the largest. The heap always holds the k smallest seen.
3Hint 3Explore hintHide hint
After processing every element, the heap's top (its maximum) is exactly the kth smallest of the whole array.
A · Core idea
Reframe 'kth smallest' as 'the largest of the k smallest'. If you could hold onto just the k smallest elements you've seen, then the biggest of those k is the kth smallest once you've seen everything.
Why a max-heap and not a min-heap. You want O(1) access to the largest of your current k keepers, because that's the candidate most likely to be evicted when a smaller element arrives. A max-heap puts that largest at the top. Push each new element; if the heap now holds k + 1 elements, pop the top (the largest) — it can't be among the k smallest. After the full pass, the heap contains exactly the k smallest elements and its top is the kth smallest.
Why the size cap makes this efficient. Every heap operation costs O(log(size)), and the size is bounded by k, not n. So even though you touch all n elements, each costs O(log k). When k is small relative to n, O(n log k) is a real win over the O(n log n) of sorting — and it never degrades, unlike quickselect.
Why this shines on streams. You never need all n elements in memory at once — only the current k keepers. That makes the heap the natural choice when data arrives incrementally or when O(k) space is the constraint. The trade is the log k factor on every element; quickselect drops that on average but demands the whole array up front and mutates it.
Symmetry note. For kth largest you'd flip to a min-heap of size k; the top would then be the kth largest. Same idea, mirrored comparator.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [7, 10, 4, 3, 20, 15], k = 3Array state
after 4
heap holds {10, 7, 4}
7C · Code with teaching comments
Reference implementation previewpublic int kthSmallest(int[] nums, int k) { PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); for (int x : nums) { maxHeap.offer(x); if (maxHeap.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
The size-k heap is the 'keep the best k seen so far' pattern — the same engine behind Top K Frequent Elements and K Closest Points. The trick is choosing the heap orientation opposite to what you're selecting: a max-heap to find a smallest, so the easiest element to discard sits at the top.
ComplexityO(n log k) time, O(k) space — n pushes, each O(log k) on a heap of size ≤ k, and at most n pops of O(log k) → O(n log k) time. The heap never exceeds k elements → O(k) space.
E · Edge cases and pitfalls3Using a min-heap by reflex — then the top is the smallest, not the kth smallest.Explore edge casesHide edge cases
Pitfalls
- Using a min-heap by reflex — then the top is the smallest, not the kth smallest.
- Forgetting the size cap — the heap grows to n and you've just sorted in O(n log n).
- In Python, forgetting to negate on the way out — returns -value.
Approach 2 of 2 · Optimal
Quickselect — Partition and Recurse One Side (Optimal)
1Hint 1Explore hintHide hint
Quicksort's partition places one pivot into its final sorted position p and splits the rest into < pivot and ≥ pivot. If p equals your target index, you're done — for free.
2Hint 2Explore hintHide hint
If p < target, the kth smallest is in the right part; if p > target, it's in the left part. Recurse (or loop) into only that side — never both.
3Hint 3Explore hintHide hint
Convert k to a 0-indexed target = k - 1. Average work is n + n/2 + n/4 + … = 2n = O(n). Guard the O(n²) worst case with a random pivot.
A · Core idea
Quickselect is quicksort with a shortcut: since you only want the element at one position, you discard the half that can't contain it.
The partition primitive (Lomuto). Pick a pivot (here nums[hi]). Sweep j from lo to hi−1, maintaining a boundary i: every element strictly less than the pivot is swapped to the left of i, and i advances. After the sweep, swap the pivot into position i. Now nums[i] is in its final sorted position — everything left of it is smaller, everything right is ≥. That returned index p = i is the pivot's true rank.
The shortcut that beats sorting. Compare p to target = k − 1. If p == target, the pivot is the kth smallest — return it immediately, no further work. If p < target, the kth smallest lies strictly to the right, so set lo = p + 1 and repeat on the right segment only. If p > target, it lies to the left, so set hi = p − 1. Crucially you recurse into one side. Quicksort recurses into both (that's why it's O(n log n)); throwing away one side is what collapses the average cost to O(n).
Why O(n) average but O(n²) worst. A balanced pivot halves the remaining range, so the work telescopes: n + n/2 + n/4 + … = 2n. But if the pivot is always the max or min — which happens on already-sorted input with last-element pivots — each step shrinks the range by just one, giving n + (n−1) + … + 1 = O(n²). The standard fix is a random pivot: before partitioning, swap a uniformly random index into hi. An adversary can no longer force bad splits, so the expected time is O(n) regardless of input order. For a hard worst-case guarantee, median-of-medians picks a provably good pivot in O(n), yielding O(n) worst case at the cost of a larger constant.
The off-by-one and over-recursion traps. (1) Using k instead of k − 1 for the target returns the element one slot off. (2) Recursing into both sides quietly turns this into quicksort — same answer, worse complexity. (3) Comparing with < vs <= inside partition affects how duplicates land but not correctness of the selected rank; keep it consistent. Say the invariant aloud — 'after partition, p is the pivot's final rank; I keep only the side containing target' — and the logic stays tight.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
nums = [7, 10, 4, 3, 20, 15], k = 3Array state
partition full
pivot 15 → p=4 > 2 → keep left [0..3]
7C · 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
The whole speedup is one decision: recurse into a single side. Sorting answers 'what is every element's rank?'; selection answers only 'what sits at rank k?' — a strictly smaller question, so it admits a strictly cheaper algorithm. That 'solve exactly what's asked, not more' instinct generalizes: binary search, two pointers, and quickselect all win by refusing to compute order they don't need.
ComplexityO(n) average, O(n²) worst time, O(1) iterative space — Each partition is O(size). On average a pivot splits roughly in half, so total work is n + n/2 + n/4 + … = 2n = O(n). Adversarial input that always picks an extreme pivot degrades to n + (n−1) + … = O(n²); a random pivot makes that effectively impossible. Iterative loop uses O(1) extra space.
E · Edge cases and pitfalls7nums = [5], k = 1 — Single element; target = 0, first partition returns p = 0 = target → returns 5.Explore edge casesHide edge cases
Edge cases handled
nums = [5], k = 1Single element; target = 0, first partition returns p = 0 = target → returns 5.nums = [2, 2, 2, 2], k = 3All duplicates; any pivot lands somewhere, but every value is 2 → returns 2 regardless of split.nums = [1, 2, 3, 4, 5], k = 1 (already sorted)The random pivot prevents the O(n²) degeneration that a fixed last-element pivot would suffer here.
Pitfalls
- Using k instead of k − 1 as the target index — returns the wrong rank.
- 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.
- Forgetting the final pivot swap in partition — the returned index isn't the pivot's true rank.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int kthSmallest(int[] nums, int k) { int lo = 0, hi = nums.length - 1, target = k - 1; 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.
1k vs k − 1 off-by-one
kth smallest is 1-indexed but arrays are 0-indexed. Targeting index k returns the (k+1)th smallest.
Explore the code comparisonHide the code comparison
k vs k − 1 off-by-one
kth smallest is 1-indexed but arrays are 0-indexed. Targeting index k returns the (k+1)th smallest.
Don't write this
int target = k; // WRONG: off by one
if (p == target) return nums[p];Write this instead
int target = k - 1; // 0-indexed rank
if (p == target) return nums[p];2Recursing into both sides
Quickselect's speed comes from discarding the half that can't hold the target. Recursing into both is just quicksort — O(n log n), not O(n) average.
Explore the code comparisonHide the code comparison
Recursing into both sides
Quickselect's speed comes from discarding the half that can't hold the target. Recursing into both is just quicksort — O(n log n), not O(n) average.
Don't write this
p = self._partition(nums, lo, hi)
self.select(nums, lo, p - 1, target) # WRONG: also 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 picking the last element as pivot makes already-sorted input degrade to O(n²) — every partition peels off just one element.
Explore the code comparisonHide the code comparison
Fixed pivot on sorted input
Always picking the last element as pivot makes already-sorted input degrade to O(n²) — every partition peels off just one 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, then recurse into one side only
Code pattern to memorize
target = k - 1 # 0-indexed rank of kth smallest
lo, hi = 0, n - 1
while lo <= hi:
p = partition(lo, hi) # Lomuto: elements < pivot go left
if p == target: return nums[p]
elif p < target: lo = p + 1 # answer is to the RIGHT
else: hi = p - 1 # answer is to the LEFTRules to remember
- 1kth smallest maps to 0-indexed rank
target = k − 1. The classic off-by-one is usingkinstead ofk − 1. - 2Quickselect recurses into one side only — that's why it's O(n) average, not O(n log n). Recursing into both is just quicksort.
- 3Lomuto partition returns the pivot's final sorted position
p. Compareptotarget: equal → done;p < target→ go right;p > target→ go left. - 4Worst case is O(n²) when the pivot is always extreme (already-sorted input). Randomize the pivot (swap a random index into
hibefore partitioning) to make that astronomically unlikely. - 5The heap baseline keeps a max-heap of size k — push, then pop the largest whenever size exceeds k. The top is the kth smallest. Use this when you want guaranteed O(n log k) with no worst-case blowup, or for a streaming input.
Use this pattern when
- You need ONE order statistic (kth smallest/largest, median), not the full sorted order
- The array is unsorted and you're allowed to mutate it (quickselect partitions in place)
- Average-case O(n) matters and the data isn't adversarial
- Streaming or memory-bounded: a size-k heap caps space at O(k)
Choose another pattern when
- You need the full sorted array anyway → just sort, O(n log n)
- Many repeated kth queries on static data → sort once, answer each in O(1)
- Worst-case guarantees are required and input may be adversarial → median-of-medians O(n) worst case, or the heap
- You may not mutate the input and can't copy it → quickselect's in-place swaps are off the table
Interview takeaway
Selection is strictly easier than sorting: you only need the kth element, not all n in order. Quickselect reuses the partition primitive but throws away half the work each step, landing at O(n) average. The size-k heap is the safe, streaming-friendly O(n log k) fallback. Knowing both — and when each wins — is the interview signal.
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 smallest/largest from an unsorted, mutable array and want O(n) average. Reuse the quicksort partition but recurse into one side only. 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 Largest Element via QuickselectComing soonSame partition; target the (n − k)th smallest, or partition for descending order.
- Kth Largest Element in a StreamComing soonA size-k min-heap maintained across an online stream of inserts.
- Median of Two Sorted ArraysSelection across two sorted arrays via binary search on the partition point.
- Top K Frequent ElementsComing soonQuickselect or a size-k heap over (value, frequency) pairs.