Faangprep Logo
Log inStart free
Browse curriculum

Kth Largest Element

The Kth Largest Element problem asks for the Kth largest element in an unsorted array, found efficiently.

A min-heap holding the K largest values seen so far keeps its smallest member at the root — so the root is the Kth largest, and it is also the test for everything that arrives next: a value no bigger than it cannot possibly belong. Switch to PUSH-POP to see what skipping that one comparison costs.

READY

Stream

7
2
9
4
12
3
15
6
11

Heap · the 3 largest so far

root

1

2

3rd largest

—

Compares

0

With guard

16

 

9 values arriving one at a time, and we want the 3rd largest. Sorting all of them would answer it, and would also answer far more than was asked — so instead keep only the 3 largest seen so far, in a heap that gives away its smallest member for free.

Next

7 arrives and the heap has room — 1 of 3. With fewer than 3 values held, nothing can be ruled out yet, so it goes in without being compared to anything but its way down.

Stream

K

Admission

Intuition

We could sort the entire array and pick the element at index N-K, but that takes O(N log N) time.

Using a Min-Heap of size K, we can iterate through the array once. The heap essentially acts as a filter, keeping only the "K largest elements seen so far". The smallest of these elite elements (the root) is exactly the Kth largest overall.

Concept

Algorithm:

  • Initialize an empty Min-Heap.
  • Iterate through every number x in the array.
  • Push x into the heap.
  • If heap size > K, pop the minimum element (remove the weakest of the "top" candidates).
  • After checking all elements, the heap root is the answer.

How it Works

The visualizer below shows the heap updating as numbers stream in.

  1. Heap: The K largest values seen so far, kept in a min-heap. The root holds the smallest of them, which is the Kth largest.
  2. Stream: Pale blue values are held in the heap, grey struck-through values were skipped or evicted, and the solid blue value is the one being handled.
  3. GUARD and PUSH-POP: GUARD compares each value with the root first and skips it if it cannot win; PUSH-POP pushes every value and removes the smallest of the K+1. The Compares readout shows the cost of each. When the stream ends, the root turns green: it is the answer.
  4. Result: Start with [3, 2, 1, 5, 6, 4] and K=2. The heap evolves: [3] -> [2,3] -> [2,3] -> [3,5] -> [5,6] -> [5,6]. Answer 5.

Step-by-Step Breakdown

1. Create MinHeap.
2. Loop x in nums.
3. heap.push(x).
4. If heap.size() > K: heap.pop().
5. Return heap.peek().

When to Use

  • Finding median in a stream.
  • Top K frequent words/numbers.
  • Near-sorted array sorting.

When NOT to Use

  • When K is very small (K=1, just linear scan).
  • When K is very large (K=N, just standard sort).

How to Identify

"Return the Kth largest...", "Find top K..."

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Introduction

Next

Introduction

Frequently Asked Questions

Heap vs Quickselect?

A Heap takes O(N log K). Quickselect (a partitioning-based algorithm) can find the Kth element in O(N) average time.

Kth Largest vs Smallest?

To find the Kth Largest, use a Min-Heap. To find the Kth Smallest, use a Max-Heap.

Why maintain exactly K items?

By keeping the heap size fixed at K, you ensure that any elements ejected are guaranteed to NOT be in the Top-K set.