Sign in
Skip to solution
mediumDSA

How does Quickselect find the kth smallest/largest element?

1.1k views
01

Understand the problem

Explain Quickselect.

quickselectarrays
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Quickselect partitions around a pivot like quicksort but recurses into only one side — the side containing the kth index. Average O(n), worst O(n²) with bad pivots (mitigated by random or median-of-medians pivots). It avoids fully sorting.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Partition, recurse one side
Run Playground
import random

def quickselect(nums, k):           # k-th smallest, 1-indexed
    target = k - 1

    def partition(lo, hi, pivot_idx):
        pivot = nums[pivot_idx]
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]   # park pivot at end
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[store], nums[i] = nums[i], nums[store]
                store += 1
        nums[hi], nums[store] = nums[store], nums[hi]           # pivot to final spot
        return store

    lo, hi = 0, len(nums) - 1
    while True:
        if lo == hi:
            return nums[lo]
        p = partition(lo, hi, random.randint(lo, hi))
        if p == target:
            return nums[p]
        elif target < p:
            hi = p - 1
        else:
            lo = p + 1


# --- demo ---
print(quickselect([7, 4, 6, 3, 9, 1], 2))   # 3  (2nd smallest)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 35 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track