Kth Largest/Smallest Elements

The previous pattern kept the top k with a heap. This one answers a subtly different question: not "give me the best k" but "give me the single element that sits at rank k," the 10th-highest score, the median, the 99th percentile. And for that one element, there is a beautiful shortcut that beats sorting outright, because it turns out you can find the k-th element without putting any of the others in order.

The idea is borrowed from quicksort and it is called QuickSelect. Quicksort partitions an array around a pivot, everything larger on one side, smaller on the other, and then recurses into both halves. But if you only want the k-th element, you know which side it is on after the very first partition, so you throw the other half away and recurse into one side only. That single change is what drops the cost from O(n log n) to O(n) on average.

QuickSelect: partition, then recurse into one side

Pick a pivot, split the array into bigger, equal, and smaller groups, and use the group sizes to decide where the k-th largest lives. Only one group is worth descending into.

import random

def quickselect(nums, k):                      # k-th largest, 1-indexed
    pivot = random.choice(nums)
    bigger  = [x for x in nums if x > pivot]
    equal   = [x for x in nums if x == pivot]
    smaller = [x for x in nums if x < pivot]
    if k <= len(bigger):
        return quickselect(bigger, k)          # the k-th largest is among the bigger
    if k <= len(bigger) + len(equal):
        return pivot                           # it is one of the pivots
    return quickselect(smaller, k - len(bigger) - len(equal))

On [55, 70, 90, 85, 60, 95, 80] asking for the 3rd largest returns 85. The reason the average cost is linear and not n log n: each partition is O(size), and discarding one side means the work shrinks geometrically, n + n/2 + n/4 + ..., which sums to about 2n. You pay linear time to answer a question that looks like it needs a sort.

The array 55 70 90 85 60 95 80 partitioned around the pivot 80 into bigger (90 85 95), equal (80) and smaller (55 70 60); seeking the 3rd largest, and since three values are bigger, only that group is searched and the rest discarded, giving linear average time.

In the wild: the p99 latency without sorting a million samples

Every team that runs a service watches percentiles. The p99 latency, the value that 99 percent of requests come in under, is the number in your SLO, and computing it means finding the element at rank 0.99 * N in a batch of latency measurements. Sorting all N samples to read off one position is the wasteful version. QuickSelect finds that one rank in O(N) average time:

def percentile(latencies, p):
    n = len(latencies)
    # p99 sits near the top: only (100 - p) percent of samples are larger,
    # so it is the k-th LARGEST with k = round((1 - p/100) * n).
    k = max(1, round((1 - p / 100) * n))       # p99 -> k ~ 0.01 * n (near the max)
    return quickselect(latencies, k)           # k-th largest, no full sort

It is exactly the k-th-element problem wearing an operations hat: a percentile is a rank, and a rank is what QuickSelect was built to find. The same routine that pulls the 10th-highest exam score pulls the p99 of a million latencies, touching each sample a constant number of times on average instead of paying to order all of them. That linear cost is why selection algorithms sit inside real monitoring and analytics pipelines.

The trigger

You need the element at one specific rank, the k-th largest or smallest, the median, a percentile, and you do not need the rest ordered. The tell is a single positional query. If you are about to sort the whole array to read off one index, QuickSelect almost certainly does it faster.

Where it shows up

  • Percentiles and medians over large batches, the median-of-medians being the deterministic cousin.
  • Threshold selection: the cutoff score for the top 5 percent, the k-th nearest neighbor's distance.
  • The partition step it shares with quicksort, useful whenever you want the array split around a rank.

Where it bites

The famous hazard is the pivot. A consistently bad pivot, always the largest or smallest remaining, degrades QuickSelect to O(n^2), the same worst case as quicksort. Choosing the pivot at random, as above, makes that essentially never happen, so never take the first element as pivot on data that might be sorted or adversarial. And remember the in-place versions reorder the input; if you need the original order preserved, work on a copy.

When it is the wrong tool

If the data is a stream, or it changes continuously, QuickSelect is the wrong shape entirely: it needs the whole array in memory at once and reorders it, so reach back for a heap, or a streaming sketch like t-digest for approximate percentiles. If you need several ranks at once, p50 and p90 and p99 together, a handful of QuickSelect calls still totals O(n) and beats sorting asymptotically; a single O(n log n) sort only pulls ahead once you want many ranks, on the order of log n of them, or you needed the whole array ordered for something else anyway. And for the top or bottom k as a set rather than a single rank, that is the heap-based Top-K pattern, not this one.

Its neighbors

It is the selection-focused sibling of Top-K Elements, which keeps a whole group rather than one rank. Its partition-and-recurse-into-one-side structure is pure Divide & Conquer, and a first cousin of Binary Search, which also discards a half each step. When "k-th" means "k-th most frequent," it teams up with Hashmaps and Frequency Counting to build the counts first.

References