Quickselect and Nth Element

To find the kth largest element you do not need the array sorted — you need one element in the right place. Sorting delivers n answers when you asked for one, and charges $O(n \log n)$ for the privilege.

Quickselect is quicksort that recurses into only the side containing the answer. Each partition discards a fraction of the array instead of processing both halves, and the geometric series $n + n/2 + n/4 + \cdots$ sums to $2n$ — so the average cost is $O(n)$.

The judgement this page builds is knowing when quickselect is genuinely the right answer, because often it is not.

What you’ll learn

• Partitioning, and why quickselect recurses once where quicksort recurses twice.
• Why $O(n)$ average and $O(n^2)$ worst case, and the one line that makes the worst case vanish in practice.
• Three-way partitioning, and why it matters when values repeat.
• The honest comparison against heaps, sorted, and bucket sort — and when each wins.
• Three real LeetCode problems solved in the browser: 215, 973, 347.

The cue

You are looking at a selection problem when…

• “kth largest / smallest / closest / most frequent” — 215, 973, 347.
• “the top k” and the order within the k does not matter — that freedom is what makes $O(n)$ possible.
• You are asked for a median as a one-off computation. (A median over a stream is Two Heaps instead.)
• The interviewer says “can you do better than sorting?” on a kth-element problem.

The anti-cue: if the output must be sorted, you cannot escape $O(k \log k)$ at least, and quickselect’s advantage shrinks. If the data arrives over time, quickselect is wrong — it needs the whole array up front and it mutates it.

Visual intuition

Quickselect is quicksort that throws away one side. The partition step is identical — watch it here, then note that quickselect recurses into only one of the two halves:

sortThe partition is shared; quickselect just stops sorting the half it does not needpartition · O(n) expected for select

7021126384553647

1def quick_sort(a, lo, hi):2    if lo >= hi:3        return4    p = partition(a, lo, hi)5    quick_sort(a, lo, p - 1)6    quick_sort(a, p + 1, hi)7 8def partition(a, lo, hi):9    pivot = a[hi]10    i = lo                      # boundary of the < pivot region11    for j in range(lo, hi):12        if a[j] < pivot:13            a[i], a[j] = a[j], a[i]14            i += 115    a[i], a[hi] = a[hi], a[i]   # pivot into place16    return i

setupQuicksort picks a pivot, moves everything smaller to its left and everything larger to its right, and then recurses. Unlike merge sort it never merges — after one partition the pivot is already in its final position forever.

Play‹›1/26⟲

Quicksort recurses into both halves, giving n log n. Quickselect compares the pivot's final index with k and recurses into one side only — so the work is n + n/2 + n/4 + ... = O(n) expected. Same partition, half the recursion tree, a different complexity class.

How it works

Partition around a pivot so that everything smaller sits left and everything larger sits right. The pivot is now at its final sorted position. Compare that position with the index you want:

• equal — done, no recursion at all;
• target is smaller — recurse left only;
• target is larger — recurse right only.

quickselect_basic.py

import random
 
 
def quickselect(nums, k):
    """Return the kth SMALLEST element (k is 0-indexed). Mutates nums."""
    lo, hi = 0, len(nums) - 1
 
    while True:
        if lo == hi:
            return nums[lo]
 
        # random pivot -- this is what avoids the O(n^2) worst case in practice
        pivot_index = random.randint(lo, hi)
        nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]
        pivot = nums[hi]
 
        store = lo                              # Lomuto partition
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
 
        if k == store:
            return nums[store]
        elif k < store:
            hi = store - 1                      # recurse LEFT only
        else:
            lo = store + 1                      # recurse RIGHT only
 
 
print(quickselect([3, 2, 1, 5, 6, 4], 4))   # 5  -- 5th smallest = 2nd largest

The loop is the tail-recursion written out, which keeps space at $O(1)$ instead of $O(\log n)$ of stack frames.

Randomise the pivot — it is not optional

With a fixed pivot (say always nums[hi]), an already-sorted array makes every partition split off exactly one element. That is $n + (n-1) + (n-2) + \cdots = O(n^2)$, and sorted input is extremely common in tests. LeetCode 215 has adversarial cases specifically designed to kill fixed-pivot quickselect.

One random.randint(lo, hi) reduces the probability of repeated bad splits to negligible. The expected time is $O(n)$ for every input, because the randomness is in your algorithm rather than in the data.

There is also a deterministic $O(n)$ worst-case variant — median-of-medians — but its constant factor is bad enough that it is rarely used in practice. Naming it is the right depth; implementing it is almost never asked.

Dry run

quickselect([3, 2, 1, 5, 6, 4], k=4)

The pivot is randomised in the real template, so this trace pins it to nums[hi] to be reproducible. The sorted array is [1, 2, 3, 4, 5, 6], so the answer at k = 4 is 5.

Window	Pivot	store after partition	Array	Decision
[0, 5]	4	3	[3, 2, 1, 4, 6, 5]	4 > 3 -> lo = 4
[4, 5]	5	4	[3, 2, 1, 4, 5, 6]	4 == 4 -> return 5

Two partitions. Three things this shows that a sort would hide:

The array is never sorted, and does not need to be. The final state is [3, 2, 1, 4, 5, 6] — positions 3, 4, 5 happen to be right, and [3, 2, 1] is still a mess. That is the entire economy of quickselect: it only orders what it must pass through. If the caller wants sorted output, this is the wrong tool.

store is a final position, not a guess. After the first partition the pivot 4 sits at index 3, and it will never move again — everything left of it is smaller, everything right is larger. That certainty is what licenses discarding a whole side instead of recursing into both, which is the one difference from quicksort.

k == store returns with no recursion at all. Step 2 finishes on the comparison, not by narrowing to a single element. The lo == hi guard at the top of the loop is the fallback for when the window shrinks to one, not the normal exit.

Why randomising the pivot is not optional, measured

nums = [1, 2, …, 20] — already sorted — searching for k = 0, the minimum:

Pivot choice	Comparisons
Fixed nums[hi]	190
Random, ten runs	22, 26, 53, 24, 33, 38, 35, 38, 19, 19

190 is exactly $n(n-1)/2$ — the worst case, achieved precisely. With a fixed last-element pivot on sorted input, every partition peels off exactly one element, so the work is $19 + 18 + \cdots + 1$. The random runs cluster around 20-40, i.e. a small multiple of n.

Sorted input is not exotic — it is one of the most common shapes in a test suite, and LC 215 has adversarial cases built for exactly this. One random.randint(lo, hi) moves the randomness out of the data and into your algorithm, which is why the expected bound becomes $O(n)$ for every input rather than for average inputs.

Three-way partitioning: [7, 7, 7, 7, 7], k = 2

Depth	Window	Pivot	< 7	== 7	> 7	Next
0	[0, 4]	7	empty	[0, 4]	empty	2 is inside the equal block -> return 7

One partition, done. Every element landed in the equal block, and k = 2 is inside it, so the answer is the pivot. Compare against the two-way version on the same input:

Input	Two-way partitions needed
[7] * 5, k = 2	3
[7] * 50, k = 25	26

26 partitions for 50 elements — about n/2, i.e. $O(n)$ partitions each doing $O(n)$ work. Two-way partitioning shuffles equal elements back and forth without shrinking the problem, because < pivot is false for all of them and they all pile up on one side of store. The equal block is what converts that into a single step.

Three-way on a mixed array with duplicates

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5], k = 5. Pivot pinned to nums[lo] for reproducibility. Sorted, the array is [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9], so the answer is 4.

Depth	Window	Pivot	Resulting split	Array	Next
0	[0, 10]	3	<: [0,3) · ==: [3,4] · >: (4,10]	[1,1,2,3,3,9,6,5,5,5,4]	5 > 4 -> right
1	[5, 10]	9	<: [5,10) · ==: [10,10]	[1,1,2,3,3,6,5,5,5,4,9]	5 < 10 -> left
2	[5, 9]	6	<: [5,9) · ==: [9,9]	[1,1,2,3,3,5,5,5,4,6,9]	5 < 9 -> left
3	[5, 8]	5	<: [5,6) · ==: [6,8]	[1,1,2,3,3,4,5,5,5,6,9]	5 < 6 -> left
4	[5, 5]	4	==: [5,5]	unchanged	5 in block -> return 4

Depth 3 is the row that earns the three-way partition: the three 5s are placed in one pass as the block [6, 8] and never examined again. Note also that a bad pivot — 9 at depth 1, the maximum — costs a level but not correctness; the window still shrank by one element, which is the worst-case behaviour the randomisation exists to make rare.

The gt-side asymmetry. When swapping from the gt end, i must not advance: the value swapped in came from an unexamined position and still needs classifying. Advancing i there skips it, which quietly misplaces elements — the array still looks partitioned and the answer is wrong. The lt side is different because the value swapped in from lt has already been seen.

Complexity, honestly

Approach	Time	Space	Notes
sorted(nums)[k]	$O(n \log n)$	$O(n)$	One line; often fast enough and the right first answer
Quickselect	$O(n)$ average, $O(n^2)$ worst	$O(1)$	Mutates the input; unordered output
Size-k heap	$O(n \log k)$	$O(k)$	Best when k is small or data streams
heapq.nsmallest(k, ...)	$O(n \log k)$	$O(k)$	Stdlib, sorted output, no mutation
Bucket / counting sort	$O(n)$	$O(n)$	Only when the value range is bounded

Quickselect is often not the best answer — say which and why

For $n = 10^5$, $\log n \approx 17$. Quickselect’s $O(n)$ beats sorting’s $O(n \log n)$ asymptotically, but with a worse constant and a randomised worst case. The genuinely better answers are frequently:

• heapq.nlargest(k, ...) when k \ll n — $O(n \log k)$, three characters of code, no mutation, and it returns them sorted.
• Bucket sort when values are bounded, as in LC 347 where frequencies cannot exceed n — a true $O(n)$ with no randomisation.

The strongest interview answer states the sorting baseline, names quickselect and its $O(n)$-average/$O(n^2)$-worst profile, then picks based on the actual constraints. Reaching straight for quickselect on LC 347, where bucket sort is cleaner and $O(n)$ worst case, reads as pattern matching rather than thinking.

Three-way partitioning

With many duplicate values, two-way partitioning wastes work: equal elements get shuffled repeatedly without shrinking the problem. A three-way (Dutch national flag) partition splits into < pivot, == pivot, > pivot, and the entire equal block is finished in one pass.

quickselect_3way.py

import random
 
 
def kth_smallest(nums, k):
    def select(lo, hi):
        pivot = nums[random.randint(lo, hi)]
        lt, i, gt = lo, lo, hi
        while i <= gt:                          # Dutch national flag
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1                         # do NOT advance i here
            else:
                i += 1
        # now: [lo, lt) < pivot,  [lt, gt] == pivot,  (gt, hi] > pivot
        if k < lt:
            return select(lo, lt - 1)
        if k > gt:
            return select(gt + 1, hi)
        return nums[k]                          # inside the equal block
 
    return select(0, len(nums) - 1)
 
 
print(kth_smallest([7, 7, 7, 7, 7], 2))   # 7 -- one partition finishes it

On [7,7,7,7,7] the first partition puts everything in the equal block and returns immediately. Two-way partitioning would recurse $O(n)$ times on the same input.

Note the asymmetry: when swapping from the gt end you must not advance i, because the value swapped in is unexamined. Advancing it there is the classic Dutch-flag bug.

The variant map

Variant	The change	Canonical problem
kth smallest	The template as written, 0-indexed	—
kth largest	Select index n - k, or negate every value	215
Top k elements (not just the kth)	Partition once at n - k; the whole right side is the answer, unordered	215 · 973
k closest to a point	Same, but partition on the distance as the key	973 K Closest Points to Origin
Top k frequent	Count first, then select over (value, count) pairs — or bucket sort, which is $O(n)$ worst case	347
Many duplicate values	Three-way (Dutch flag) partition; the equal block finishes in one pass	215 with heavy duplicates
Median	Select at n // 2; for an even count select twice	4 · 462
Wiggle / partition into halves	Select the median, then three-way partition around it	324 Wiggle Sort II
Streaming, k fixed	Quickselect needs the whole array — use a size-k heap instead	703 Kth Largest in a Stream
Deterministic $O(n)$ worst case	Median-of-medians pivot; name it, do not implement it	—
Bounded value range	Counting or bucket sort — a true $O(n)$ with no randomisation	347 · 692

Selecting the top k is cheaper than sorting them

A common misread: LC 215 asks for the kth largest element, so one partition at index n - k and a single array read answers it. But even when the problem wants all top k, quickselect still applies — after partitioning at n - k, the entire right side is the answer set, in arbitrary order, at $O(n)$ expected.

Sort that slice only if the problem demands order, and then it is $O(n + k \log k)$ rather than $O(n \log n)$. Noticing that “the top k” and “the top k, sorted” are different requirements is worth a sentence out loud.

Practice — real LeetCode problems

LC 215 — Kth Largest Element in an Array · Medium

Problem. Given an integer array nums and an integer k, return the kth largest element. Note this is the kth largest in sorted order, not the kth distinct element.

Constraints. 1 <= k <= len(nums) <= 10^5, -10^4 <= nums[i] <= 10^4. Can you solve it without sorting?

Examples. nums = [3,2,1,5,6,4], k = 2 gives 5 · nums = [3,2,3,1,2,4,5,5,6], k = 4 gives 4

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Convert the “kth largest” into an ascending index once, at the top: target = len(nums) - k. Doing that conversion up front avoids a whole class of off-by-one errors that come from carrying “largest” semantics through the recursion.

Then partition and recurse into whichever side contains target.

Time $O(n)$ expected, $O(n^2)$ worst case (astronomically unlikely with a random pivot). Space $O(1)$ for the partitioning, plus $O(\log n)$ expected recursion depth — convertible to $O(1)$ by looping instead.

([7,7,7], 2) is the duplicate case: three-way partitioning resolves it in one step, while a two-way version recurses repeatedly on identical values.

Two answers worth giving alongside:

• heapq.nlargest(k, nums)[-1] — $O(n \log k)$, one line. Genuinely better when k is small.
• sorted(nums)[-k] — $O(n \log n)$, the baseline. State it, then improve on it.

Follow-ups you should expect: “What if you cannot mutate the input?” — copy first ($O(n)$ space) or use a heap. “kth distinct largest?” — deduplicate into a set first, which changes the answer. “Streaming (LC 703)?” — quickselect cannot; a size-k min-heap can. “Guarantee $O(n)$ worst case?” — median-of-medians; name it and note the constant factor makes it impractical.

LC 973 — K Closest Points to Origin · Medium

Problem. Given an array of points on the plane and an integer k, return the k closest points to the origin, by Euclidean distance. The answer may be returned in any order.

Constraints. 1 <= k <= len(points) <= 10^4, -10^4 <= xi, yi <= 10^4.

Examples. points = [[1,3],[-2,2]], k = 1 gives [[-2,2]] · points = [[3,3],[5,-1],[-2,4]], k = 2 gives [[3,3],[-2,4]]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Two observations do most of the work:

1. Never compute a square root. $\sqrt{a} < \sqrt{b}$ exactly when $a < b$ for non-negative values, so comparing $x^2 + y^2$ gives the same ordering with integer arithmetic — faster, and no floating-point tie-breaking weirdness.
2. “Any order” is permission to be fast. If the result had to be sorted by distance you would pay $O(k \log k)$ regardless.

heapq.nsmallest: $O(n \log k)$ time, $O(k)$ space. Idiomatic and hard to get wrong.

Quickselect on squared distance: $O(n)$ average, $O(1)$ extra space, and returns points[:k] after partitioning. Better asymptotically, more code, mutates the input.

For $n = 10^4$ these are close in practice. State both, note that nsmallest wins on clarity while quickselect wins on asymptotics, and pick one. A max-heap of size k (pushing and popping the farthest) is a third $O(n \log k)$ answer worth mentioning — it is the one that extends to a stream.

Follow-ups you should expect: “The points arrive as a stream?” — a size-k max-heap works; quickselect cannot. “Sorted by distance?” — nsmallest already returns sorted; after quickselect you sort just the k. “Closest to an arbitrary point, not the origin?” — subtract that point first. “Ties in distance?” — the problem accepts any, so no special handling.

LC 347 — Top K Frequent Elements · Medium

Problem. Given an integer array nums and an integer k, return the k most frequent elements, in any order.

Constraints. 1 <= len(nums) <= 10^5, the answer is guaranteed unique. Your algorithm must be better than $O(n \log n)$.

Examples. nums = [1,1,1,2,2,3], k = 2 gives [1,2] · nums = [1], k = 1 gives [1]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Count frequencies in $O(n)$, then select the top k counts. The interesting part is how you select, and this is the problem where quickselect is not the best answer.

Method	Time	Note
Sort the counts	$O(n \log n)$	Explicitly ruled out by the constraints
most_common(k)	$O(n \log k)$	Uses a heap internally; clean and fast
Size-k heap by hand	$O(n \log k)$	Same, spelled out
Quickselect on counts	$O(n)$ average	Randomised worst case $O(n^2)$
Bucket by frequency	$O(n)$ worst case	Frequencies are bounded by n

Bucket sort wins here and is worth knowing, because the value range is bounded: no frequency can exceed len(nums), so you can index directly.

python

buckets = [[] for _ in range(len(nums) + 1)]
for value, count in Counter(nums).items():
    buckets[count].append(value)
out = []
for count in range(len(buckets) - 1, 0, -1):     # walk from high to low
    for value in buckets[count]:
        out.append(value)
        if len(out) == k:
            return out

That is a genuine $O(n)$ with no randomisation — strictly better than quickselect’s expected $O(n)$. Recognising a bounded range and reaching for counting/bucket techniques is the transferable lesson.

most_common(k) is the answer to write first: it satisfies the better-than-$O(n \log n)$ requirement, is one line, and is obviously correct. Then offer the bucket version when asked to beat $O(n \log k)$.

Follow-ups you should expect: “Truly $O(n)$?” — bucket by frequency. “Ties?” — the problem guarantees uniqueness; otherwise clarify the tie-break (LC 692 makes it lexicographic, which changes the comparator). “Top k frequent words (LC 692)?” — same counting, but the tie-break forces a custom sort key. “Streaming?” — counts change over time; you need a heap plus lazy deletion, or a count-min sketch for approximate answers at scale.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 692 is where a naive comparator falls apart

Top K Frequent Words needs descending frequency but ascending lexicographic order on ties. In a min-heap you cannot simply negate both, because one direction must flip and the other must not. The clean fix is a key of (-count, word) with heapq.nsmallest, or a wrapper class with a custom __lt__. See Sorting with Custom Comparators for the general technique.

5 problems

0 easy5 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○347Top K Frequent ElementsmediumBucket by frequency for a true $O(n)$; the range is boundedNeetCode 150Blind 75amazonmetauberbytedance
• ○215Kth Largest Element in an ArraymediumThe base quickselect; randomise the pivotNeetCode 150LeetCode Top Interview 150
• ○324Wiggle Sort IImedium
• ○692Top K Frequent WordsmediumLexicographic tie-break makes the comparator the hard part
• ○973K Closest Points to OriginmediumSelect on squared distance -- never take a square rootNeetCode 150

Interview follow-ups

They ask	What they’re checking	The answer
“Better than sorting?”	Whether you know selection exists	Quickselect: $O(n)$ average by recursing into one side only
“Why $O(n)$?”	Whether you can justify it	Each partition discards a constant fraction, so $n + n/2 + n/4 + \cdots = 2n$
“Worst case?”	Honesty	$O(n^2)$ if pivots split badly; a random pivot makes that negligible, and median-of-medians makes it $O(n)$ guaranteed at a bad constant
“Quickselect or a heap?”	Judgement	Heap when k is small, data streams, or you must not mutate; quickselect when the whole array is in memory and k is comparable to n
“Many duplicates?”	Depth	Three-way partitioning finishes the equal block in one pass
“Can you avoid mutating the input?”	Care	Quickselect reorders in place; copy first or use a heap
“Truly $O(n)$ worst case here?”	Recognising bounded ranges	If values (or counts) are bounded, bucket/counting sort gives $O(n)$ with no randomisation

Edge-case checklist

• k == 1 and k == len(nums) — the extremes of the range.
• Single element — ([1], 1) must work with no partitioning.
• All identical values — [7,7,7]; the case three-way partitioning exists for.
• Already sorted, or reverse sorted — the fixed-pivot killer; proves you randomised.
• Negative values — fine for comparisons; only a problem if you assumed non-negative for bucketing.
• kth largest vs. kth distinct largest — different answers; clarify.
• Duplicates in the answer region — LC 215 counts repeats, so [3,2,3,1,2,4,5,5,6] with k=4 gives 4.
• Mutating the caller’s list — a real design concern; note it or copy.

Self-check

pch.quizTag pch.quizDefaultTitle

1. What does quickselect do differently from quicksort?

   A It uses a three-way partition instead of a two-way one B After partitioning it recurses into only one side, because the pivot's position is final and tells you which side holds index k C It partitions around the median instead of a random element D It sorts in place rather than allocating a new array
   pch.quizShowAnswer

   B — After partitioning it recurses into only one side, because the pivot's position is final and tells you which side holds index k — Partitioning puts the pivot at its final sorted position, so comparing that position with k rules out an entire side with certainty. Quicksort must sort both halves; quickselect discards one. That single change is what turns O(n log n) into O(n) expected -- the recurrence becomes n + n/2 + n/4 + ... = 2n rather than n log n.

2. You use a fixed pivot of nums[hi] and the input is already sorted. What happens?

   A Nothing -- sorted input is the best case for quickselect B Every partition peels off exactly one element, giving n(n-1)/2 comparisons -- 190 for n = 20, the exact worst case C The algorithm returns a wrong answer D It degrades to O(n log n), the same as sorting
   pch.quizShowAnswer

   B — Every partition peels off exactly one element, giving n(n-1)/2 comparisons -- 190 for n = 20, the exact worst case — Measured on [1..20] searching for the minimum: 190 comparisons with a fixed pivot, which is exactly n(n-1)/2. Ten random-pivot runs on the same input ranged from 19 to 53. Sorted input is one of the most common shapes in a test suite, and LC 215 ships adversarial cases built for this. The fix is one line.

3. Why does randomising the pivot give an O(n) expected bound for *every* input, not just average ones?

   A Because random numbers are uniformly distributed B The randomness lives in the algorithm rather than the data, so no fixed input can be adversarial against it C Because it guarantees the pivot is close to the median D It does not -- the worst case is still O(n^2) for sorted input
   pch.quizShowAnswer

   B — The randomness lives in the algorithm rather than the data, so no fixed input can be adversarial against it — This is the distinction between average-case and randomised analysis. An adversary who knows your code but not your coin flips cannot construct a bad input, because badness depends on the flips. The worst case is still O(n^2) -- it just now requires improbable luck rather than a particular input. Median-of-medians gives a deterministic O(n) worst case, but with a constant factor bad enough that naming it is the right depth.

4. For [7, 7, 7, 7, 7] with k = 2, how do two-way and three-way partitioning compare?

   A Both finish in one partition B Three-way finishes in one partition; two-way needs O(n) of them -- 26 partitions for n = 50 C Two-way is faster because it does less work per pass D Three-way fails on all-equal input
   pch.quizShowAnswer

   B — Three-way finishes in one partition; two-way needs O(n) of them -- 26 partitions for n = 50 — Three-way puts every element in the equal block on the first pass, and k lands inside it, so the pivot is the answer. Two-way asks `< pivot`, which is false for all of them, so they all pile on one side of store and the window shrinks by one per pass -- measured at 3 partitions for n = 5 and 26 for n = 50. Each of those partitions is O(n), so the total is quadratic.

5. In the Dutch-flag partition, why must `i` not advance after swapping with the `gt` end?

   A To keep the loop condition `i <= gt` valid B The value swapped in came from an unexamined position and still needs classifying C Because gt decreases, so i would overshoot D It should advance; not advancing is the bug
   pch.quizShowAnswer

   B — The value swapped in came from an unexamined position and still needs classifying — The classic Dutch-flag bug. Values below `i` have been classified; values at and above `gt` have not. Swapping from `gt` brings an unknown value to position `i`, so it must be examined next iteration. The `lt` side is genuinely different -- the value coming from `lt` was already seen. Advance `i` on the `gt` swap and elements are silently misplaced: the array still looks partitioned and the answer is wrong.

6. LC 347 asks for the k most frequent elements. Is quickselect the best answer?

   A Yes -- O(n) average beats the alternatives B No -- frequencies are bounded by n, so bucket sort is O(n) worst case, cleaner, and needs no randomisation C Yes, but only with a three-way partition D No -- a size-k heap is always better for this problem
   pch.quizShowAnswer

   B — No -- frequencies are bounded by n, so bucket sort is O(n) worst case, cleaner, and needs no randomisation — A count cannot exceed n, so you can index buckets directly by frequency and read them off in one pass: true O(n) with a deterministic worst case. Quickselect on the (value, count) pairs works and is a fine second answer, but reaching for it here reads as pattern matching rather than looking at the constraint. A size-k heap is O(n log k), the right answer when k is very small or the data streams.

7. The problem asks for all k largest elements, not just the kth. Does quickselect still apply?

   A No -- quickselect returns a single element B Yes -- partition once at index n - k and the whole right side is the answer set, unordered, at O(n) expected C Only if you run it k times D Yes, but it costs O(k n)
   pch.quizShowAnswer

   B — Yes -- partition once at index n - k and the whole right side is the answer set, unordered, at O(n) expected — Partitioning at n - k places every one of the k largest to the right of that index, in arbitrary order. If the problem needs them sorted, sorting just that slice is O(n + k log k), still better than O(n log n) for the whole array. Noticing that "the top k" and "the top k, sorted" are different requirements is worth a sentence out loud.

8. When should you *not* reach for quickselect?

   A When n is large -- the constant factor makes it lose to sorting B When the input must not be mutated, when the data streams, or when a bounded value range makes counting sort a deterministic O(n) C When k is greater than n / 2 D When the array contains duplicates
   pch.quizShowAnswer

   B — When the input must not be mutated, when the data streams, or when a bounded value range makes counting sort a deterministic O(n) — Quickselect mutates in place, needs the whole array resident, and has a randomised worst case. `heapq.nlargest(k, ...)` is O(n log k), three characters of code, non-mutating, and returns sorted output -- often the better answer when k is much smaller than n. A stream rules quickselect out entirely; use a size-k heap. Duplicates are handled fine with a three-way partition.

Recall card

• Partition, then recurse into one side only. The pivot’s post-partition index is its final sorted position, so comparing it with k discards a whole side with certainty. That is the only difference from quicksort, and it is what gives $O(n)$ expected: $n + n/2 + n/4 + \cdots = 2n$.
• Randomise the pivot — one line, not optional. Fixed nums[hi] on sorted input costs exactly $n(n-1)/2$: 190 comparisons for n = 20, against 19-53 with a random pivot.
• Randomised, not average-case. The randomness is in the algorithm, so no input can be adversarial — only bad luck can.
• Write the loop, not the recursion. Tail position, so iterating keeps space at $O(1)$.
• k == store returns immediately. The lo == hi guard is the fallback, not the normal exit.
• Heavy duplicates need three-way (Dutch flag). All-equal input: one partition instead of ~n/2 (measured 26 for n = 50).
• On the gt swap, do not advance i — that value is unexamined. The classic Dutch-flag bug, and it misplaces elements silently.
• The array comes back unsorted, and mutated. If the caller needs order or an untouched input, this is the wrong tool.
• kth largest = select at n - k. For all top k, one partition at n - k and take the right side; sort that slice only if order is required, at $O(n + k \log k)$.
• Frequently not the best answer: heapq.nlargest is $O(n \log k)$ and non-mutating; bucket sort is a deterministic $O(n)$ when values are bounded (LC 347); a stream needs a size-k heap. State the sorting baseline, then choose from the constraints.

Recap

• Quickselect is quicksort that recurses into one side only, giving $O(n)$ average instead of $O(n \log n)$ — because $n + n/2 + n/4 + \cdots = 2n$.
• Randomise the pivot. A fixed pivot is $O(n^2)$ on sorted input, and sorted input is common in tests.
• Convert “kth largest” to an ascending index once, at the top.
• Three-way partitioning for duplicate-heavy data — the equal block finishes in a single pass, and do not advance i when swapping from the gt end.
• Quickselect is not automatically the right answer. A size-k heap wins for small k, streams, and immutable input; bucket sort wins outright when the value range is bounded (LC 347).
• Selection needs the whole array in memory. For medians over a stream, use Two Heaps.

Next: Top K Elements — the heap-based view of the same family, and the patterns where a heap is the only option.