1603. The kth Smallest, Without Sorting

Given n integers and a number k, print the kth smallest value, counting from 1. Values may repeat, and repeats are counted separately.

3 1 4 1 5, k = 2 -> 1 sorted: 1 1 3 4 5 5 5 5 5, k = 3 -> 5 7, k = 1 -> 7

## What most people try first

Sort and index, which is correct and O(n log n). That is a perfectly good answer and worth saying out loud, because the interesting question is what it does that the problem did not ask for: it puts ALL n values in order when only one position was wanted.

## Partition, then recurse into one side only

Pick a pivot and split the values into those below it, those equal to it, and those above:

select(arr, k): pivot = some element of arr lo = values < pivot; eq = values == pivot; hi = values > pivot if k <= len(lo): return select(lo, k) if k <= len(lo) + len(eq): return pivot return select(hi, k - len(lo) - len(eq))

The difference from merge sort is that only ONE side is explored. Merge sort recurses into both halves and does O(n) work per level, giving n log n. Here the work per level is still O(n), but the array shrinks each time, so with a balanced split the total is

n + n/2 + n/4 + ... = 2n

which is O(n), not O(n log n). A geometric series that sums to a constant multiple of its first term is the whole reason this is faster, and it is the reason to recognise the one-sided recursion as its own pattern.

## Why three parts and not two

With duplicates, splitting into "less than" and "not less than" can fail to shrink the array at all: on 5 5 5 5 5 with pivot 5, everything lands in the second part and the recursion never terminates. Pulling the equal values into their own group guarantees the pivot itself is removed from both recursive sides, so every call is strictly smaller.

## The cost that is not O(n)

A bad pivot gives O(n^2). If the pivot is always the smallest value, each call removes one element and the series becomes n + (n-1) + ... = n^2 / 2. On an already-sorted array, choosing the first element as pivot does exactly that.

Choosing the MIDDLE element, as below, defeats the sorted and reverse-sorted cases, which are the ones that actually appear. A random pivot makes the expected cost O(n) whatever the input, at the price of a non-deterministic run.

## Overflow

Values reach 10^9 in magnitude and the algorithm only ever COMPARES them, never adds two together, so a signed 32 bit integer suffices. The count k is at most n, which is 2 * 10^5. Nothing here overflows.

## Cost

O(n) expected with a reasonable pivot, O(n^2) worst case, and O(1) extra space if the partition is done in place rather than into new lists.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ n` - `-10^9 ≤ each value ≤ 10^9` - values may repeat