← DSA Atlas
Dedicated problem page · #215

Kth Largest Element in an Array

MediumHeap and Priority QueueBounded min-heap of size kBinary heap (priority queue)
Solve on LeetCode ↗
215
MediumHeap and Priority QueueBinary heap (priority queue)Bounded min-heap of size k

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array. This is the kth largest in sorted order, not the kth distinct element. You must solve it without fully sorting.

Open official problem prompt ↗
In plain English

Find the value that would sit at position k from the top if the array were sorted in descending order, without paying for a full sort.

Picture it like this

Imagine judging a talent show and only keeping the top k acts on a shortlist. Each new act bumps out the current weakest of the shortlist if it is better. At the end, the weakest act still on the shortlist is exactly the kth best overall.

Example
Input
nums = [3, 2, 1, 5, 6, 4], k = 2
Output
5
Why
Sorted descending is [6, 5, 4, 3, 2, 1]; the 2nd largest is 5.
Constraints
1 <= k <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4
Pattern lesson

See the pattern, then code

Bounded min-heap of size k
Recognition clue

You need the kth largest (or smallest) element but not a full ordering — a signal to keep only the k best seen so far in a heap.

↗
Heap and Priority Queue

Top k, kth value, repeated minimum extraction, scheduling, or merging sorted streams.. If you keep a min-heap that never grows past size k, its smallest element (the root) is always the kth largest among everything processed. Anything smaller than the root can never be the answer once k bigger values exist.

New words, made simpleKnow these before the algorithm
Min-heap
A tree-shaped structure whose smallest element is always at the root and retrievable in O(1).
kth largest
The element at index k-1 when values are listed from largest to smallest, counting duplicates.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Sort then index

Simple and correct, but sorts everything when you only need one position.

Sort the array descending and return the element at index k-1.

Time O(n log n)Space O(1) to O(n)
Quickselect

Fastest on average but has a quadratic worst case and is trickier to write correctly.

Partition around a pivot like quicksort but only recurse into the side containing the kth position.

Time O(n) average, O(n^2) worstSpace O(1)
Best choiceSize-k min-heap

Robust worst-case bound, tiny memory when k is small, and ideal for streaming input.

Keep a min-heap capped at size k; its root is the kth largest.

Time O(n log k)Space O(k)
The rule we keep true

Invariant

After processing the first i elements, the heap holds the k largest of those i values (or all of them if i < k), with the kth largest at the root.

Why this is correct

Reasoning

A value only leaves the heap when k strictly larger values remain, so it can never be the kth largest. Anything that survives is therefore among the top k, and the smallest survivor is precisely the kth largest.

The algorithm in three movesSay these aloud before coding
1Push each element onto a min-heap

after 3,2: heap=[2,3]

2Whenever the heap exceeds size k, pop the smallest

after 1 (pop 1): heap=[2,3]

3After processing all elements the root is the kth largest

after 5 (pop 2): heap=[3,5]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
30
21
12
53
64
45
1 · Read3, 2
2 · AskHeap under size k=2?
3 · Update stateheap = [2, 3]
4 · ResultBoth kept; heap now full.
Key takeaway

The heap retains only the 2 largest values seen; its root 5 is the answer.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6Empty heap

    Start with no candidates; Python lists are heaps via the heapq module.

  2. 2
    Lines 7-8Push each value

    Every element is a potential top-k member, so it enters the heap.

  3. 3
    Lines 9-10Cap the size

    Popping the smallest whenever size exceeds k evicts values that can no longer be the answer.

  4. 4
    Lines 11Return the root

    The remaining smallest of the surviving k values is the kth largest overall.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • k equals the array length (return the minimum)
  • k = 1 (return the maximum)
  • arrays containing duplicates, e.g. nums = [3,3,3,3], k = 2 returns 3
  • negative numbers
!

Common beginner mistakes

  • Confusing kth largest with kth distinct largest — duplicates are counted
  • Using a max-heap of all elements and popping k times, which costs O(n + k log n) memory O(n) — heavier than needed
  • Off-by-one: the kth largest is the min-heap root, not a value you pop
Check your understanding

Why keep a MIN-heap when you want the LARGEST elements?

More in Heap and Priority Queue

#295Find Median from Data StreamTwo balanced heaps#373Find K Pairs with Smallest Sumsk-way merge with a heap#502IPOGreedy with a max-heap of affordable options#621Task SchedulerFill idle slots around the most frequent task#692Top K Frequent WordsCount then heap-order by frequency and word#703Kth Largest Element in a StreamFixed-size min-heap (bounded top-k)