Kth Smallest Element (Quickselect)

Kth Smallest Element asks for a single ranked value — the k-th smallest — without caring about the order of everything else. Sorting the whole array would answer it, but that is more work than the question needs. Quickselect does just enough partitioning to pin down one position, and it runs in O(n) on average.

The slow way first

The obvious move is to sort the array and return nums[k - 1]. That is correct and only a couple of lines, but sorting is O(n log n) — and it does far more than asked. We arranged all six values just to read one of them.

The question to ask: do I really need the whole array ordered, or only the value at one position? We only need index k - 1. Quickselect exploits that: it places one pivot in its final sorted slot per round and throws away the half that cannot contain our target.

The idea: partition, then recurse into one side

Quickselect borrows the partition step from quicksort. Pick a pivot (here, the last element). Sweep across the window with two pointers: j scans, and i marks the boundary so that everything left of i is <= pivot. Each value <= pivot is swapped to position i, then i advances. At the end we drop the pivot at i — now the pivot is in its final sorted position p.

Then compare p to k - 1:

Because we keep only one side each round, the work roughly halves: n + n/2 + n/4 + ... which sums to O(n) on average.

Walk through it

Step through the animation for [7, 4, 6, 3, 9, 1], k = 3 (target index 2). Watch the pivot light up, the pointers i and j sweep, and a swap slide the pivot into place as p. After each partition, the discarded side dims:

• Pivot 1 lands at index 0. p = 0 < 2 → keep the right side.
• Pivot 7 lands at index 4. p = 4 > 2 → keep the left side.
• Pivot 3 lands at index 1. p = 1 < 2 → keep the right side.
• Pivot 4 lands at index 2. p = 2 == 2 → that is the answer, 4.

Pseudocode

partition(l, r):                  # Lomuto; pivot is the last element
    pivot = a[r]; i = l
    for j from l to r - 1:
        if a[j] <= pivot:
            swap a[i], a[j]       # drag a small value to the boundary
            i = i + 1
    swap a[i], a[r]              # drop the pivot at its final slot
    return i                     # the pivot index p
 
select(k):
    l = 0; r = n - 1
    loop:
        p = partition(l, r)
        if p == k - 1: return a[p]   # pivot is exactly the answer
        if p < k - 1:  l = p + 1     # answer is to the right
        else:          r = p - 1     # answer is to the left

The Python solution

def partition(a, l, r):
    pivot, i = a[r], l
    for j in range(l, r):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[r] = a[r], a[i]
    return i
 
def select(a, k):
    l, r = 0, len(a) - 1
    while l <= r:
        p = partition(a, l, r)
        if p == k - 1:
            return a[p]
        elif p < k - 1:
            l = p + 1
        else:
            r = p - 1

• partition uses the Lomuto scheme: pivot = a[r], and i is the boundary where the next small value goes.
• Inside the loop, a[j] <= pivot is the test; when it holds we swap a[j] to the boundary and bump i.
• After the sweep, a[i], a[r] = a[r], a[i] drops the pivot at index i — its final sorted position.
• select runs partitions in a loop instead of recursing. Line 14 is the win: if p == k - 1, the pivot is the answer and we stop early.
• Lines 16-19 shrink the search to one side — l = p + 1 (look right) or r = p - 1 (look left) — never both.

Complexity

Partitioning is in-place, so beyond the array itself we use O(1) extra space (the loop version avoids recursion stack entirely). The average O(n) beats sorting because we discard half the work each round.

When this pattern shows up

Practice