Kth smallest and largest element in an unsorted array
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
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);