⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#215) before relying on it.

Kth Largest Element in an Array

An interactive visualization of the min-heap approach. Watch how a min-heap of size k is maintained to efficiently find the kth largest element without fully sorting the array.

Heap / Priority Queue LeetCode 215 ↗ Medium

The Problem

Given an integer array nums and an integer k, return the k^th largest element in the array.

Note that it is the k^th largest element in sorted order, not the k^th distinct element.

Can you solve it without sorting? Use a min-heap of size k: iterate through the array, maintain a heap of at most k elements. At the end, the heap's minimum (the root) is the kth largest element.

Interactive Visualization

Array (comma-separated)

Preset

Speed:

Array & Heap Visualization

Min-Heap (size ≤ k = 2)

Empty

Code

import java.util.PriorityQueuefun findKthLargest(nums: IntArray, k: Int): Int {    val heap = PriorityQueue<Int>()    for (num in nums) {        heap.add(num)        if (heap.size > k) {            heap.poll()        }    }    return heap.peek()!!}

import heapqdef findKthLargest(nums, k):    heap = []    for num in nums:        heapq.heappush(heap, num)        if len(heap) > k:            heapq.heappop(heap)    return heap[0]

Status

Press Step or Play to begin.

How It Works

Key Insight

Instead of sorting the entire array, we maintain a min-heap of size k. As we iterate through the array, the heap always holds the k largest elements seen so far. The smallest of those k elements sits at the top of the min-heap. When we finish processing all elements, that heap root is exactly the kth largest element in the array.

Why a Min-Heap?

A min-heap lets us efficiently access and remove the smallest element. By capping the heap at size k, we ensure that anything smaller than the current kth largest gets evicted. After processing all elements, only the k largest remain, and the root (minimum of those k) is our answer.

The Algorithm

Initialize: Create an empty heap
For each element in the array:
- Push the element onto the min-heap
- If heap size > k: pop the minimum element (the root). This evicts the smallest of the k+1 elements, keeping only the k largest.
Return heap[0]: The root of the min-heap is the kth largest element

Complexity

Time O(n log k)

Space O(k)

We iterate through all n elements, and each heap push/pop operation takes O(log k) time since the heap never exceeds size k. This is better than sorting (O(n log n)) when k is much smaller than n. The space complexity is O(k) for the heap storage.