K-th Element Patterns

"QuickSelect for O(n), heap for O(n log k), binary search for implicit structures."

Finding the k-th smallest/largest element or the top k elements appears in many forms. QuickSelect gives O(n) average for a single k-th element. A size-k heap gives O(n log k) for top-k from a stream. Binary search on value works for implicit structures like sorted matrices.

16 min readheap problems →

Problems you can solve with this pattern

5 problems · click any to start solving

All heap →

1Kth Largest Element in an ArrayMediumSolve

2K Closest Points to OriginMediumSolve

3K-th Smallest Element in a Sorted MatrixMediumSolve

4Kth Smallest in Lexicographical OrderHardSolve

QuickSelect — find k-th smallest in O(n) average

function quickSelect(nums, k) {
    // Find k-th smallest (0-indexed: k=0 means smallest)
    const partition = (lo, hi) => {
        // Random pivot to avoid O(n²) worst case
        const pivotIdx = lo + Math.floor(Math.random() * (hi-lo+1));
        [nums[pivotIdx], nums[hi]] = [nums[hi], nums[pivotIdx]];
        const pivot = nums[hi];
        let i = lo;
        for (let j = lo; j < hi; j++)
            if (nums[j] <= pivot) [nums[i], nums[j]] = [nums[j], nums[i++]];
        [nums[i], nums[hi]] = [nums[hi], nums[i]];
        return i; // pivot's final position
    };
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        const p = partition(lo, hi);
        if (p === k) break;
        if (p < k) lo = p + 1;
        else hi = p - 1;
    }
    return nums[k];
}

// For k-th LARGEST: call quickSelect(nums, nums.length-k)
// Or negate all values and find k-th smallest

K-th element problems test algorithm selection. Sort and index is O(n log n) — too slow when O(n) is possible. The right approach depends on the structure: QuickSelect for arrays, heap for streaming/top-k, binary search for implicit sorted structures like matrices or function values.

Problem Type	Best Approach	Time
K-th smallest in unsorted array	QuickSelect (partition)	O(n) avg
K largest elements from stream	Min-heap of size k	O(n log k)
K-th smallest in sorted matrix	Binary search on value	O(n log(max-min))
K-th smallest in BST	Inorder traversal, stop at k	O(k)
Median of two sorted arrays	Binary search on partition	O(log min(m,n))
K-th smallest pair sum	Min-heap multi-source BFS	O(k log k)
K closest points	QuickSelect or max-heap	O(n) or O(n log k)

QuickSelect — O(n) Average

QuickSelect — find k-th smallest in O(n) average

function quickSelect(nums, k) {
    // Find k-th smallest (0-indexed: k=0 means smallest)
    const partition = (lo, hi) => {
        // Random pivot to avoid O(n²) worst case
        const pivotIdx = lo + Math.floor(Math.random() * (hi-lo+1));
        [nums[pivotIdx], nums[hi]] = [nums[hi], nums[pivotIdx]];
        const pivot = nums[hi];
        let i = lo;
        for (let j = lo; j < hi; j++)
            if (nums[j] <= pivot) [nums[i], nums[j]] = [nums[j], nums[i++]];
        [nums[i], nums[hi]] = [nums[hi], nums[i]];
        return i; // pivot's final position
    };
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        const p = partition(lo, hi);
        if (p === k) break;
        if (p < k) lo = p + 1;
        else hi = p - 1;
    }
    return nums[k];
}

// For k-th LARGEST: call quickSelect(nums, nums.length-k)
// Or negate all values and find k-th smallest

Binary Search on Value for Implicit Structures

K-th smallest in sorted matrix — binary search on answer

// Sorted matrix: each row and column is sorted ascending
// Count elements <= mid, check if count >= k
function kthSmallestMatrix(matrix, k) {
    const n = matrix.length;
    let lo = matrix[0][0], hi = matrix[n-1][n-1];

    const countLEQ = (target) => {
        let count = 0, row = n-1, col = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= target) { count += row + 1; col++; }
            else row--;
        }
        return count;
    };

    while (lo < hi) {
        const mid = lo + ((hi-lo) >> 1);
        if (countLEQ(mid) >= k) hi = mid; // mid might be the answer
        else lo = mid + 1;
    }
    return lo; // lo = smallest value where count >= k (must exist in matrix)
}

Kth Largest Element in an Array

Medium

Solve

K Closest Points to Origin

Medium

Solve

K-th Smallest Element in a Sorted Matrix

Medium

Solve

Kth Smallest in Lexicographical Order

Hard

Solve

K-th Largest Element in a Stream

Easy

Solve

K-th element algorithm selector:
- Array, single k-th → QuickSelect O(n) average
- Stream / online (elements arrive one by one) → min-heap of size k
- Sorted matrix → binary search on value O(n log range)
- BST k-th smallest → inorder traversal, stop at k
- Two sorted arrays, median → binary search on partition O(log min(m,n))
- Lexicographic k-th → count prefix sizes, skip/descend O(log²n)
- Top-k from multiple sorted lists → min-heap with pointers O(k log k)

← Cycle Detection Array Manipulation Tricks →