Quickselect and Nth Element

To find the kkth largest element you do not need the array sorted — you need one element in the right place. Sorting delivers nn 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, sortedsorted, and bucket sort — and when each wins.
Three real LeetCode problems solved in the browser: 215, 973, 347.

The cue

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

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.

With a fixed pivot (say always nums[hi]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)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.

Complexity, honestly

Approach	Time	Space	Notes
`sorted(nums)[k]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-`kk` heap	$O(n \log k)$	$O(k)$	Best when `kk` is small or data streams
`heapq.nsmallest(k, ...)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

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, ...)heapq.nlargest(k, ...) when k \ll nk \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 nn — 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== 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

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][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 gtgt end you must not advance ii, because the value swapped in is unexamined. Advancing it there is the classic Dutch-flag bug.

Practice — real LeetCode problems

LC 215 — Kth Largest Element in an Array · Medium

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

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

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

Editorial — approach, complexity, follow-ups

Convert the “kth largest” into an ascending index once, at the top: target = len(nums) - ktarget = 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 targettarget.

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)([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]heapq.nlargest(k, nums)[-1] — $O(n \log k)$ , one line. Genuinely better when kk is small.
sorted(nums)[-k]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-kk 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 pointspoints on the plane and an integer kk, return the kk closest points to the origin, by Euclidean distance. The answer may be returned in any order.

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

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

Editorial — approach, complexity, follow-ups

Two observations do most of the work:

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.
“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.nsmallestheapq.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]points[:k] after partitioning. Better asymptotically, more code, mutates the input.

For $n = 10^4$ these are close in practice. State both, note that nsmallestnsmallest wins on clarity while quickselect wins on asymptotics, and pick one. A max-heap of size kk (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-kk max-heap works; quickselect cannot. “Sorted by distance?” — nsmallestnsmallest already returns sorted; after quickselect you sort just the kk. “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 numsnums and an integer kk, return the kk most frequent elements, in any order.

Constraints. 1 <= len(nums) <= 10^51 <= 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 = 2nums = [1,1,1,2,2,3], k = 2 gives [1,2][1,2] · nums = [1], k = 1nums = [1], k = 1 gives [1][1]

Editorial — approach, complexity, follow-ups

Count frequencies in $O(n)$ , then select the top kk 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)most_common(k)`	$O(n \log k)$	Uses a heap internally; clean and fast
Size-`kk` 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 `nn`

Bucket sort wins here and is worth knowing, because the value range is bounded: no frequency can exceed len(nums)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

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)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

#	Problem	Difficulty	The twist
215	Kth Largest Element in an Array	Medium	The base quickselect; randomise the pivot
973	K Closest Points to Origin	Medium	Select on squared distance — never take a square root
347	Top K Frequent Elements	Medium	Bucket by frequency for a true $O(n)$ ; the range is bounded
692	Top K Frequent Words	Medium	Lexicographic tie-break makes the comparator the hard part

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 `kk` is small, data streams, or you must not mutate; quickselect when the whole array is in memory and `kk` is comparable to `nn`
“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 == 1k == 1 and k == len(nums)k == len(nums) — the extremes of the range.
Single element — ([1], 1)([1], 1) must work with no partitioning.
All identical values — [7,7,7][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][3,2,3,1,2,4,5,5,6] with k=4k=4 gives 44.
Mutating the caller’s list — a real design concern; note it or copy.

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 ii when swapping from the gtgt end.
Quickselect is not automatically the right answer. A size-kk heap wins for small kk, 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Quickselect and Nth Element

What you’ll learn

The cue

How it works

Complexity, honestly

Three-way partitioning

Practice — real LeetCode problems

LC 215 — Kth Largest Element in an Array · Medium

LC 973 — K Closest Points to Origin · Medium

LC 347 — Top K Frequent Elements · Medium

LeetCode problem set

Interview follow-ups

Edge-case checklist

Recap

Was this page helpful?