intermediate9 min read·Updated September 30, 2026

Kth Largest Element (Heap) Explained: Finding 5 in [3, 2, 1, 5, 6, 4]

Master the Kth largest element using a min-heap with a complete walkthrough of [3, 2, 1, 5, 6, 4] for k=2, mental models, and $O(N \log k)$ complexity.

By Learnisim AI·Published September 30, 2026
LEARNING ARCSetup → Model in the example → Full trace → Twist → Edge cases → Apply
PREREQUISITES
  • Basic array manipulation
  • Understanding of binary heaps and priority queues
  • Big-O time complexity notation
Kth Largest Element via Min-Heap (k = 2, nums = [3, 2, 1, 5, 6, 4]) The Trap: Full Sorting 1. Sort all: [6, 5, 4, 3, 2, 1] 2. Pick index k-1 -> 5 Cost: O(N log N) time Wastes CPU ordering low values we will immediately discard! The Min-Heap Window Model (k = 2) Stream: 3,2,1,5,6,4 Min-Heap (max cap: 2) Root Smallest of top k Evicts min if size > k Final Answer 5 Root holds 2nd largest Worked Step-by-Step Trace Through [3, 2, 1, 5, 6, 4] for k = 2 1. Process 3 Push 3 [ 3 ] Size 1 <= 2 No pop needed 2. Process 2 Push 2 [ 2, 3 ] Size equals k (2) Root is min (2) 3. Process 1 Push 1 (size 3) Pop min (1) Heap restored [ 2, 3 ] 4. Process 5 Push 5 (size 3) Pop min (2) Top candidates [ 3, 5 ] 5. Process 6 Push 6 (size 3) Pop min (3) Top candidates [ 5, 6 ] 6. Process 4 Push 4 (size 3) Pop min (4) Final Heap Root = 5
2nd largest in [3, 2, 1, 5, 6, 4] overview diagram
Why

Why Sorting the Whole Array for the Kth Largest Element Fails at Scale

Phase 1: The Trap of Full Sorting

Imagine you are handed an unsorted collection of items, such as nums = [3, 2, 1, 5, 6, 4], and asked to find the 2nd largest element where . Your first instinct is likely to reach for a built-in sort function. If you sort the entire list in descending order, you get [6, 5, 4, 3, 2, 1] and pick index 1, which gives you 5. That feels simple, correct, and completely natural.
Now scale that problem up. What if nums contains 100,000,000 elements, but you only care about the single value when ? Sorting the entire array requires time and forces your CPU to order millions of items that you will immediately discard. You are paying a massive time penalty to organize data you do not care about.
To see why this hurts, look at the cost breakdown. Sorting rearranges every single pair, even the ones at the very bottom of the magnitude spectrum (like sorting 1 and 2 in our working example). But to find the 2nd largest element, do we really need to know that 1 comes before 2? Of course not. We only need to maintain a tiny window of the largest candidates encountered so far.
This gap between what we need (the top items) and what a full sort does (everything) is the exact problem the Kth largest element (heap) pattern solves. Instead of a full-scale reorganization, we want a streaming or bounded memory structure that discards irrelevance on the fly.
Why Full Sorting Fails for Kth Largest Element (k = 2) Phase 1: The Trap of Full Sorting O(N log N) Input: [3, 2, 1, 5, 6, 4] Sort Every Item 6 5 4 3 2 1 k=2 Found here (Index 1) ⚠️ Massive Waste at Scale (e.g. 100M items): • CPU wastes cycles ordering bottom items (1, 2, 3) • Forces O(N log N) time complexity • We organize millions of items we immediately discard Phase 2: Min-Heap Solution O(N log k) Maintain a strict window of size k = 2 5 (Min) 6 1, 2, 3, 4 discarded ✨ Why Min-Heap Wins at Scale: • Memory capped at size k (ignores irrelevant items) • Runs in O(N log k) instead of O(N log N) • Root of heap is always our exact answer (5) Shift to
Why Sorting the Whole Array for the Kth Largest Element Fails at Scale diagram
Model

The Min-Heap Window Model: Bounding Memory to Size $k$

Phase 2: The Min-Heap Window

When we look at our working example nums = [3, 2, 1, 5, 6, 4] and k = 2, we do not need to hold all 6 numbers in a sorted structure at once. Instead, imagine a fixed-size cage or window that can hold exactly elements. We want this window to always contain the largest elements seen so far. To make decisions efficiently, we structure this window as a min-heap.
A min-heap is a binary tree where every parent node is smaller than or equal to its children. This means the absolute root of the heap is always the smallest element currently inside the heap. In our window, the root acts as a strict threshold gatekeeper: any new number smaller than or equal to the root cannot possibly be in the top 2 overall, so we reject it immediately.
As we stream through [3, 2, 1, 5, 6, 4], we push each number into our min-heap. The moment the heap size exceeds , we pop the smallest element (the root). By evicting the smallest element whenever capacity overflows, we guarantee that only the largest contenders survive. When the input stream ends, the root of our min-heap is precisely the -th largest element we seek—in this case, 5.
python
import heapq

# Conceptual representation of a min-heap window of size k=2
heap = []
# After processing [3, 5], the heap looks like [3, 5] where 3 is the root (min).
# Incoming 6 replaces 3 because 6 > 3, leaving [5, 6].
The Min-Heap Window Model: Finding K-th Largest (k = 2, nums = [3, 2, 1, 5, 6, 4]) Incoming Stream (Left to Right) 3 2 1 5 6 4 Stream processing Threshold Gatekeeper (Root is Min) • Heap size strictly bounded to size k = 2. • Root = smallest element in window. • If new ≤ root → REJECT immediately! Push & Overflow Check Min-Heap Window (Capacity k = 2) 3 ROOT (Min) Evicted if overflow 5 Contender 1 6 Contender 2 State after processing [3, 2, 1, 5, 6, 4]: Heap holds [5, 6]. The smallest (3) was popped. Result: Root is 2nd Largest = 5 1 Push Element Stream nums into min-heap window O(N log k) total time 2 Check & Evict If size > k, pop smallest root Keeps top k elements only 3 Extract Result Stream ends, root is answer Heap root = 5 (2nd largest)
The Min-Heap Window Model: Bounding Memory to Size $k$ diagram
Worked example

Tracing the Min-Heap Through [3, 2, 1, 5, 6, 4] for $k = 2$

Phase 3: Worked Example

Now let us walk through our locked example step by step using a min-heap of size on the input array [3, 2, 1, 5, 6, 4]. Recall the core invariant from our model: the root of our min-heap always holds the smallest element currently among our top candidates.

Given

- Array: nums = [3, 2, 1, 5, 6, 4]
- Target rank: (we want the 2nd largest element)
•Heap capacity: max 2 elements

Steps

1.Process 3: Heap is empty. Push 3.

- Heap: [3]
2. Process 2: Push 2. Heap becomes [2, 3] (root is 2).
- Heap size (2) equals .
3. Process 1: Push 1. Heap becomes [1, 2, 3] (size ). We pop the minimum (1).
- Heap: [2, 3]
4.Process 5: Push

5. Heap becomes [2, 3, 5] (size ). We pop the minimum (2).
- Heap: [3, 5]
5.Process 6: Push

6. Heap becomes [3, 5, 6] (size ). We pop the minimum (3).
- Heap: [5, 6]
6. Process 4: Push 4. Heap becomes [4, 5, 6] (size ). We pop the minimum (4).
- Heap: [5, 6]

Result

After exhausting all elements in nums, we inspect the root of our min-heap. The root is 5, which is precisely the 2nd largest element in the array.
Try this: Given nums = [3, 2, 1, 5, 6, 4] and k = 2, trace the exact heap state after processing the number 5.
Phase 3: Worked Example (k = 2) Focus Step: Processing 5 → Heap [2, 3, 5] → Pop min (2) → Heap [3, 5] Input Stream nums = [3, 2, 1, 5, 6, 4] 3 2 1 5 Current 6 4 Push 5 Step 4a: Push 5 (Size = 3 > k) Heap temporarily becomes [2, 3, 5] 2 Min (Pop!) 3 5 Exceeds capacity k=2! Must remove minimum element (root 2) Step 4b: Pop Minimum → Heap [3, 5] Size returns to k = 2. Root is now 3. 3 New Root 5 max Invariant Maintained Min-heap root (3) guards the top k boundary.
Tracing the Min-Heap Through [3, 2, 1, 5, 6, 4] for $k = 2$ diagram
Practice

Predicting the Min-Heap State for a New Value

Phase 4: Practice

Let us test your understanding of how the min-heap window gatekeeps elements. Recall our running working example with and , which ultimately left us with a min-heap containing at the end of the array, returning 5.
Suppose we extend our tracking window by processing one more element. Imagine the algorithm encounters a new incoming value of 7 right after finishing the initial array . You must determine how the min-heap structure reacts when this new item arrives.
Work through the update mentally using the rules established in the model phase: push the new value into the heap, restore the min-heap property, and evict the smallest element if the heap size exceeds . Consider what values reside in the heap and which element sits at the root position.
Try this: Given a min-heap holding [5, 6] for k = 2, we push the new incoming value 7.
1.What is the state of the heap immediately after pushing 7 (before any pop)?
2.What element is popped, and what is the final heap state and returned kth largest value?
Apply

Transferring the Min-Heap Pattern to Dynamic Stream Processing

Phase 5: Applying the Min-Heap to Data Streams

We started with our static array nums = [3, 2, 1, 5, 6, 4] and , building a min-heap that maintained the top elements and left us with 5 at the root. But what happens when the data doesn't arrive all at once? Real-world systems often receive numbers one by one in an infinite stream where you cannot store or sort the entire history.
Because our min-heap invariant only cares about keeping the largest elements bounded inside a heap of size , the exact same logic transfers directly to online data streams. Instead of processing a pre-loaded array, a class like KthLargest maintains the heap in memory across continuous add(val) calls. Every time a new number enters the stream, you push it to the min-heap, check if the size exceeds , and pop the minimum if necessary.

Transfer Challenge

Imagine you are designing a live telemetry dashboard that must report the 2nd largest temperature reading (k = 2) as sensors broadcast data continuously.
Given the initial stream values [3, 2, 1, 5, 6, 4] which establish our familiar min-heap state of size with root 5, predict what happens when a new temperature reading of 10 arrives from the stream.
Question:
When 10 is added to the active min-heap containing the final state from our working example, what are the new contents of the heap, what element is popped, and what value does the stream now report as the 2nd largest?
python
class KthLargestStream:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = []
        # Initialize with our working example data [3, 2, 1, 5, 6, 4]
        for num in nums:
            self.add(num)
            
    def add(self, val: int) -> int:
        # TODO: Implement push, size check, and pop
        pass

FAQ

What is the min-heap state when finding the 2nd largest in [3, 2, 1, 5, 6, 4] with k = 2?
As elements are processed, the min-heap maintains a size of 2 containing the top 2 largest elements. At the end, the heap contains [5, 6], and the root (min of the top 2) is 5.
Why use a min-heap instead of a max-heap to find the Kth largest element?
A min-heap of fixed size acts as a guard that evicts the smallest element among the largest seen so far. The root of this min-heap naturally holds the Kth largest element.
What is the time and space complexity of using a heap for the Kth largest element?
The time complexity is because we insert into a heap of size for elements. The space complexity is to store the heap.
Can this approach handle duplicate elements in the array?
Yes, duplicate elements are treated as distinct values based on their occurrences, and the min-heap correctly maintains the Kth largest value even with duplicates present.

Keep learning