Get started

Quickselect Coding Problems: 3 Questions with Solutions

3 quickselect coding problems — 3 medium — with solutions in 13 languages. Plus a step-by-step walkthrough and a 2-day plan.

  • Problems: 3
  • By difficulty: 3 medium
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Quickselect finds the k-th smallest value without sorting everything. It partitions the array around a pivot, as quicksort does, then continues into only the side that holds position k, so the work shrinks geometrically — n, about n/2, about n/4 — for linear time on average. The problems here practise the partition step, choosing the pivot at random so that no input forces the quadratic worst case, and turning "k-th largest" or "k closest" into the right position.

How quickselect works, step by step

nums1021324364759687pivot< 44thrange = 2..3answer = 4
The k-th smallest number, with quickselect. Example: nums = [9, 4, 7, 1, 8, 3, 2, 6], k = 4
  1. The 4th smallest number is the one that would sit at index 3 if the array were sorted. Quickselect sorts only enough to find it: partition around a pivot, then keep the one side that can hold index 3.
  2. Partition 0..7 around its last number, 6: everything smaller moves to its left and everything larger to its right, in one pass.
  3. 6 lands at index 4, its place in sorted order, with 4 smaller numbers before it. Index 3 is to its left, so the 3 larger numbers on its right are dropped without being sorted.
  4. Only 0..3 is left. Partition it the same way, around its last number, 2.
  5. 2 lands at index 1, its place in sorted order. Index 3 is to its right, so only 2..3 can hold the answer and the one smaller number on its left is dropped.
  6. Only 2..3 is left. Partition it the same way, around its last number, 4.
  7. 4 lands at index 3, the very index we wanted, so 4 is the 4th smallest. Each round kept one side only, about n + n/2 + n/4 + … ≈ 2n steps: O(n) on average, O(n²) if every pivot is the worst.

Quickselect study plan

All 3 Quickselect problems (3 medium) over 2 days, about 2 h in all — the pattern first, then easiest to hardest. Then move on to Heap.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

Day 2

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Next topic: Heap

Quickselect: the essentials

When to reach for it

"The k-th largest", "the k-th smallest", "the median", "the k closest": one position of the sorted order, or the items below it, but not the order itself. Sorting costs O(n log n), a Heap capped at k O(n log k), and quickselect O(n) on average.

The pattern

Pick a random pivot and split the values into below, equal and above. If position k falls among the equal ones, the pivot is the answer; otherwise continue in the side that holds k, shifting k when it is the upper side. The k-th largest is position n − k + 1 in ascending order. In-place versions, with Lomuto's or Hoare's partition, narrow a [lo, hi] range instead of building lists.

import random

def kth_smallest(nums, k):          # k is 1-based; average O(n)
    pivot = random.choice(nums)
    lo = [x for x in nums if x < pivot]
    hi = [x for x in nums if x > pivot]
    if k <= len(lo):
        return kth_smallest(lo, k)
    if k > len(nums) - len(hi):
        return kth_smallest(hi, k - (len(nums) - len(hi)))
    return pivot                    # every copy of pivot sits between lo and hi

Cost

About n + n/2 + n/4 + … ≈ 2n steps: O(n) on average, O(n²) when every pivot is an extreme. The lists above take O(n) extra space; in place it is O(1). Median of medians guarantees O(n) but is slower in practice.

Common mistakes

  • Always pivoting on the first or last element, so already-sorted input costs O(n²).
  • A two-way partition, such as Lomuto's, on many equal values: an array of identical numbers shrinks by one element per round.
  • Mixing up 1-based k, a 0-based index, and largest with smallest.
  • Expecting the k low items to come out sorted; K Closest Points to Origin has to sort them afterwards.

Start with

All quickselect problems

Medium (3)

Companies that ask quickselect problems

Next topic: Heap