Pattern Reference
K-th Element
"Quickselect, median of medians, k-th smallest in sorted matrix, k-th largest in stream."
Loading...
Deep Dive Tutorial
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 smallestBinary 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)
}Worked Problems
trophy
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)
- 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)