How does Quickselect find the kth smallest/largest element?

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

**Target Audience:** Beginners preparing for coding interviews — you should know arrays and loops; partitioning and pivots are explained from scratch. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output, step count and ordering claim below was produced by actually running the Python programs in the **Verified** section. ## 1. Why This Even Matters — A Story First A teacher has 30 exam papers in a messy pile and wants the paper with the **10th lowest** score — not a fully sorted pile, just that one paper. Sorting all 30 is wasteful. Instead she grabs a random paper — say it scored 62 — and makes two piles: papers below 62 on the left, papers 62 and above on the right. She counts the left pile: 14 papers. So the 10th lowest is somewhere in that left pile, and the right pile can go straight back in the drawer

The problem

Question presented to candidate: "Explain how Quickselect finds the kth smallest element of an unsorted list without sorting it, then implement it in Python. Also tell me how you would get the kth largest, and what its running time is."

What a strong answer should cover:

The baselines: sorted(nums)[k - 1] in O(n log n) and a heap in O(n log k).
Partition places the pivot at its final sorted index p; Quickselect keeps only the side that contains the target index. kth largest is index n - k.
Average O(n) (the n + n/2 + n/4 + ... argument), worst case O(n²), O(1) extra space when done in place.
Random pivots to avoid sorted-input worst cases, three-way partition for many duplicates, median of medians for a guaranteed O(n).
Python specifics: tuple swaps, copying with list(nums) so the caller's list is not reordered, a loop instead of recursion (the default recursion limit is 1000), and heapq.nsmallest / sorted as practical alternatives.

Code / implementation expected: Yes — an iterative in-place quickselect(nums, k) with a Lomuto partition in Python.

quickselect
arrays

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know arrays and loops; partitioning and pivots are explained from scratch. Difficulty: Medium Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output, step count and ordering claim below was produced by actually running the Python programs in the Verified section.

1. Why This Even Matters — A Story First

A teacher has 30 exam papers in a messy pile and wants the paper with the 10th lowest score — not a fully sorted pile, just that one paper.

Sorting all 30 is wasteful. Instead she grabs a random paper — say it scored 62 — and makes two piles: papers below 62 on the left, papers 62 and above on the right. She counts the left pile: 14 papers. So t

The solution is hidden so you can try first

11 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonQuickselect for the kth smallest and kth largest on eight inputs

Practice

PythonTrace every partition round and check against a sorted copy

Practice

PythonCount comparisons: last-element pivot vs random pivot vs three-way partition