Kth smallest number
Problem
Given an unsorted array and k, return the kth smallest element (k = 1 means the minimum). Sorting is O(n log n). Aim for O(n log k), or O(n) on average.
Example 1
Input: arr = [7, 10, 4, 3, 20, 15], k = 3 Output: 7
Also asked as: kth smallest element · Find the Kth max and min element of an array · Kth smallest number again · Kth smallest number
Test cases
Case 1
Input: [7,10,4,3,20,15], 3 Expected: 7
Case 2
Input: [7,10,4,3,20,15], 4 Expected: 10
Case 3
Input: [2,2,1], 2 Expected: 2
Case 4
Input: [3,1,2], 3 Expected: 3
Case 5
Input: [5], 1 Expected: 5
View solutionHide solution3 approaches
1. Max-heap of size k
Time O(n log k)Space O(k)
Keep the k smallest seen so far in a max-heap; its root is the answer.
// uses the MinHeap/MaxHeap idea; here with a sorted array for brevityfunction kthSmallest(a, k) { const heap = []; // acts as a max-heap of size k (kept sorted desc) for (const x of a) { if (heap.length < k) heap.push(x), heap.sort((p, q) => q - p); else if (x < heap[0]) { heap[0] = x; heap.sort((p, q) => q - p); } } return heap[0];}With a real binary max-heap the per-element work is O(log k) instead of O(k log k).
2. Quickselect
Time O(n) avg, O(n²) worstSpace O(1)
Partition like quicksort but only recurse into the side containing index k−1. Average linear.
function kthSmallest(a, k) { let lo = 0, hi = a.length - 1; const target = k - 1; while (lo < hi) { const pivot = a[hi]; let i = lo; for (let j = lo; j < hi; j++) if (a[j] < pivot) [a[i], a[j]] = [a[j], a[i]], i++; [a[i], a[hi]] = [a[hi], a[i]]; if (i === target) return a[i]; if (i < target) lo = i + 1; else hi = i - 1; } return a[lo];}3. Sort
Time O(n log n)Space O(1)
Sort and index. Simplest; the baseline you state first.
const kthSmallest = (a, k) => [...a].sort((x, y) => x - y)[k - 1];