Kth Largest Element in an Array

Medium#215k largest

You get an array of integers and a number k. Return the k-th largest number: the one that would stand k-th if the array were sorted from largest to smallest. Repeats count, so it is not the k-th distinct value. Our example: [5, 9, 2, 9, 4, 7] and k = 3 — the answer is 7, since the two 9s take first and second place.

215 Kth Largest Element in an ArrayWalkthrough · 1×

Example: [5, 9, 2, 9, 4, 7], k = 3. Top row: the numbers; below, the min-heap that keeps the 3 largest read so far.

592947min-heapk = 3
not read yetx, just pushedin the heaproot, popped nextpoppedk-th largest

The heap will keep the 3 largest numbers read so far

01/23
restart · back · play · step
Speed
1function findKthLargest(nums, k):
2 heap = empty min-heap
3 for each x in nums:
4 push x into heap
5 if size of heap > k:
6 pop min from heap
7 return min of heap
state
x
–
heap
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. After each step the heap holds the k largest numbers read so far: whenever there are k + 1, the smallest of them is popped, and it cannot be among the k largest.
  2. At the end the heap holds the k largest of the whole array. The smallest of them, the root, is the k-th largest.
  3. Each copy of a number is pushed on its own, so the two 9s take two places, and the answer is 7, as sorting would give.

Complexity

Time O(n log k): n pushes and at most n pops, each on a heap of at most k + 1 numbers. Memory O(k) for the heap.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.