mediumDSA

How does Quickselect find the kth smallest/largest element?

Q: How does Quickselect find the kth smallest/largest element?

**Intuition.** Quickselect borrows quicksort's **partition** but throws away half the work: after partitioning around a pivot, the pivot lands in its final sorted position p . If p is the index you want, you're done; otherwise recurse into **only the side** that contains the target. No full sort needed. partition; recurse into only the side holding index k < pivot

1.1k views

Understand the problem

Explain Quickselect.

quickselectarrays

Attempt it yourself

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

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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)

Join the discussion

Discussion (0)

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

How do you add two numbers stored as linked lists?

How do you implement a queue using two stacks?