AlgoViz
HomeHeap / Priority Queue

Kth Largest Element

Medium

A size-k min-heap of the biggest so far

In simple words

Keep only the k biggest numbers in a small pile; the smallest of those is your k-th largest.

The idea

Keep a min-heap of size k. Push each number; if the heap grows past k, pop the smallest. The heap's root is always the kth largest seen.

3
2
1
5
6
4
0
1
2
3
4
5
k2

Step 1 of 4. Brute force: find the largest 2 time(s), removing it each round. Values: 3, 2, 1, 5, 6, 4. k 2.

1/4
Brute force
timeO(n·k)spaceO(1)

Select k times.

1for (let r = 0; r < k; r++) {2  const i = indexOfMax(remaining);3  answer = nums[i];4  remove(i);5}

Input

array
[3, 2, 1, 5, 6, 4]

Memory

k
2
round
—

Output

1st
—
2nd
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [3, 2, 1, 5, 6, 4], k = 2
Output:
5
Explanation:
Sorted, the 2nd biggest is 5.

Example 2

Input:
nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output:
4
Explanation:
The 4th largest value is 4.

Example 3

Input:
nums = [1], k = 1
Output:
1
Explanation:
Only element is the largest.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.