Coding problem · Medium · Heap / Priority Queue
Kth Largest Element in an Array
Medium Algorithms & data structures Most askedSeen at Meta, Amazon, Microsoft, Spotify
Given an integer array nums and an integer k, return the k-th largest element (in sorted order, not the k-th distinct). Can you do better than sorting?
Example 1
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
Example 2
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4
Hints
Hint 1
Keep a min-heap of the k largest values seen so far; its top is the answer.
Hint 2
Quickselect averages O(n).
Write and run your solution
Loading the editor… (JavaScript is required to run code in your browser.)
Solution and explanation
Show the solution
Time O(n log k) · Space O(k)
A min-heap of size k: push each value, pop when the heap exceeds k. The heap then holds the k largest values and its minimum is the k-th largest — O(n log k). Quickselect (partition like quicksort, recurse into one side) is O(n) on average and is a good follow-up answer. JavaScript and PHP have no built-in heap, so their references use SplMinHeap (PHP) and a small binary heap (JS).
Reference solution
function findKthLargest(nums, k) {
const heap = []; // min-heap
const up = (i) => {
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const down = (i) => {
for (;;) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l] < heap[m]) m = l;
if (r < heap.length && heap[r] < heap[m]) m = r;
if (m === i) return;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
};
for (const x of nums) {
heap.push(x);
up(heap.length - 1);
if (heap.length > k) {
heap[0] = heap.pop();
down(0);
}
}
return heap[0];
}
function findKthLargest(nums: number[], k: number): number {
// Quickselect: average O(n).
const target = nums.length - k;
const a = [...nums];
let lo = 0, hi = a.length - 1;
while (lo < hi) {
const pivot = a[hi];
let store = lo;
for (let i = lo; i < hi; i++) {
if (a[i] < pivot) { [a[i], a[store]] = [a[store], a[i]]; store++; }
}
[a[store], a[hi]] = [a[hi], a[store]];
if (store === target) return a[store];
if (store < target) lo = store + 1; else hi = store - 1;
}
return a[lo];
}
import heapq
def find_kth_largest(nums: list[int], k: int) -> int:
heap: list[int] = []
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap)
return heap[0]
<?php
function findKthLargest(array $nums, int $k): int
{
$heap = new SplMinHeap();
foreach ($nums as $x) {
$heap->insert($x);
if ($heap->count() > $k) {
$heap->extract();
}
}
return $heap->top();
}
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int x : nums) {
heap.add(x);
if (heap.size() > k) heap.poll();
}
return heap.peek();
}
}