45. Kth Largest Confidence Score via Quickselect

Problem

A streaming transcription pipeline emits a per-segment confidence score for every recognized fragment in a batch. To set a dynamic acceptance threshold, an engineer wants the kth-largest confidence score out of a large batch, computed on every batch, so a full O(n log n) sort each time is wasteful.

Given the unsorted scores, return the kth largest without fully sorting. k is 1-indexed (k=1 means the single largest score). This must run in average O(n) time using quickselect (partition-based selection), not a full sort.

Source: src/45_kth_largest_confidence_quickselect.py

def kth_largest_confidence(scores: list[float], k: int) -> float:

>>> kth_largest_confidence([0.92, 0.55, 0.81, 0.73, 0.64], 2)
0.81

>>> kth_largest_confidence([0.4, 0.4, 0.4], 1)
0.4

Step-by-Step Approach

1. Translate "kth largest" into an ascending-sorted-index target: the kth largest is the element that would sit at index n - k if the array were fully sorted ascending.
2. Pick a pivot (a random index, to avoid the O(n²) worst case on adversarial or already-sorted input) and partition the array around it, so everything smaller ends up to its left and everything larger to its right.
3. After partitioning, the pivot sits at its final sorted position, pivot_idx. Compare it to the target index.
4. If pivot_idx == target, you're done — return that value. If pivot_idx < target, the answer is to the right, so recurse (or loop) only on the right sub-range. Otherwise recurse only on the left sub-range.
5. Because each step only recurses into one side (never both, unlike quicksort), the expected work halves geometrically, giving average O(n) instead of O(n log n).
6. Handle the base case where the search range collapses to a single index — that element is the answer regardless of further partitioning.

The key insight is that quickselect throws away the partition it doesn't need instead of recursing into both, which is exactly what turns an O(n log n) sort into an average O(n) selection.

Reference solution

import random


def _partition(arr, lo, hi, pivot_idx):
    pivot_val = arr[pivot_idx]
    # move pivot to the end out of the way
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    store = lo
    for i in range(lo, hi):
        if arr[i] < pivot_val:
            arr[store], arr[i] = arr[i], arr[store]
            store += 1
    # move pivot into its final sorted position
    arr[store], arr[hi] = arr[hi], arr[store]
    return store


def kth_largest_confidence(scores: list[float], k: int) -> float:
    arr = list(scores)
    n = len(arr)
    # kth largest == the element at ascending-sorted index (n - k)
    target = n - k
    lo, hi = 0, n - 1
    while True:
        if lo == hi:
            return arr[lo]
        # random pivot avoids the O(n^2) worst case on adversarial/sorted input
        pivot_idx = random.randint(lo, hi)
        pivot_idx = _partition(arr, lo, hi, pivot_idx)
        if pivot_idx == target:
            return arr[pivot_idx]
        elif pivot_idx < target:
            lo = pivot_idx + 1
        else:
            hi = pivot_idx - 1

Key Functions & Tricks

• random.randint(lo, hi) — randomized pivot choice, defeats adversarial inputs that would make a fixed pivot choice O(n²).
• Lomuto partition — single left-to-right scan that places the pivot at its final sorted index in O(hi - lo) time.
• target = n - k — converts "kth largest" into the equivalent ascending-order index to search for.
• One-sided recursion — unlike quicksort, only the sub-range containing the target is ever explored, which is what gives average O(n) instead of O(n log n).
• lo == hi base case — a single-element range is trivially its own answer.

How to Recognize This Pattern