Kth smallest number

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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 brevity
function 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];