Kth smallest and largest element in an unsorted array

Medium

Problem

Given an unsorted array of distinct values and k, return the kth smallest and the kth largest element.

Example 1

Input:  arr = [7, 10, 4, 3, 20, 15], k = 3
Output: kth smallest 7, kth largest 10

Also asked as: Kth smallest and largest element in an unsorted array · “k” largest element in an array

Test cases

Case 1

Input:    [7,10,4,3,20,15], 3
Expected: 10

Case 2

Input:    [7,10,4,3,20,15], 1
Expected: 20

Case 3

Input:    [7,10,4,3,20,15], 6
Expected: 3

Case 4

Input:    [5], 1
Expected: 5

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. One heap of size k

Time O(n log k)Space O(k)

Kth largest → min-heap of size k (root is the answer). Kth smallest → max-heap of size k. Quickselect gives average O(n).

function kthLargest(a, k) {
const h = []; // min-heap as sorted array for brevity
for (const x of a) {
let i = h.findIndex((v) => v > x);
i === -1 ? h.push(x) : h.splice(i, 0, x);
if (h.length > k) h.shift();
}
return h[0];
}
const kthSmallest = (a, k) => kthLargest(a, a.length - k + 1);