LeetCode 215: Kth Largest Element in an Array Using a Min Heap

Today I solved LeetCode 215: Kth Largest Element in an Array.

The problem looks simple at first. We are given an array nums and an integer k, and we need to return the kth largest element.

For example:

nums = [3, 2, 1, 5, 6, 4]
k = 2

Answer = 5

The important part of the problem is this:

Can we solve it without sorting the entire array?

That immediately made me think about a heap.

Understanding What We Actually Need

Suppose:

nums = [3, 2, 1, 5, 6, 4]
k = 2

We are looking for the second largest element.

One approach would be to sort everything:

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

Then we can easily find 5.

But do we actually care about the ordering of all six numbers?

No.

We really only care about the 2 largest elements:

[5, 6]

This gives us the first important idea:

Instead of keeping track of every element, we can keep only the k largest elements we have seen so far.

Why Use a Heap?

A heap is useful when we repeatedly need quick access to the smallest or largest element.

Python’s heapq gives us a min heap by default.

Initially, I thought about the fact that we are looking for the kth largest element, so using a min heap might seem strange.

But the important question is not:

How do I quickly get the largest element?

The better question is:

Among the k largest elements I am keeping, which element do I want to remove when a better candidate appears?

Suppose:

k = 2

and we currently have:

[5, 6]

Now we encounter:

4

Temporarily, our candidates are:

[4, 5, 6]

But we only want to keep two elements.

Which one should we remove?

The smallest one:

4

That is exactly what a min heap is good at.

So the idea becomes:

Keep a min heap containing the k largest elements seen so far.

Maintaining a Heap of Size K

We start with an empty heap:

min_k = []

Then we process every number:

for num in nums:
    heapq.heappush(min_k, num)

Every number gets pushed into the heap.

But we do not want the heap to keep growing.

We only want k elements.

So after pushing a number, we check:

if len(min_k) > k:

If this is true, the heap has become too large.

We remove its smallest element:

heapq.heappop(min_k)

This is an important detail about Python’s heapq.

heappop() takes the whole heap:

heapq.heappop(min_k)

We do not need to find the smallest element ourselves.

The heap already knows where it is.

Why Does This Keep the K Largest Elements?

Every time the heap grows beyond k, we remove the smallest element.

Imagine:

k = 2

and we temporarily have:

[4, 5, 6]

We remove:

4

and keep:

[5, 6]

So smaller elements keep getting removed while the larger elements survive.

After processing the entire array, the heap contains exactly the k largest elements.

That gives us the key invariant:

At any point after trimming the heap, it contains the k largest elements seen so far, or all elements seen so far if fewer than k have been processed.

Why Is the Answer at Index 0?

Now comes the part that makes the whole solution click.

Get EverythingGuy’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

A Python min heap guarantees:

min_k[0]

is the smallest element in the heap.

Suppose at the end:

k = 2

and the heap contains:

[5, 6]

Among these:

6 = largest
5 = second largest

The smallest element among the 2 largest elements is exactly the 2nd largest element overall.

More generally:

The smallest element among the k largest elements is the kth largest element.

So our answer is simply:

return min_k[0]

Final Approach

The algorithm is:

1. Create an empty min heap.
2. Go through every number in nums.
3. Push the number into the heap.
4. If the heap contains more than k elements, remove the smallest element.
5. After processing everything, the heap contains the k largest elements.
6. Return the smallest element in that heap.

Python Solution

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        min_k = []
        for num in nums:
            heapq.heappush(min_k, num)
            if len(min_k) > k:
                heapq.heappop(min_k)
        return min_k[0]

Time Complexity

Let:

n = number of elements in nums

We process every element once.

For each element, we perform a heap push:

heapq.heappush()

and sometimes a heap pop:

heapq.heappop()

The heap contains at most k + 1 elements during processing.

Heap operations therefore take:

O(log k)

Since we process n elements:

Time Complexity: O(n log k)

Space Complexity

We only keep k elements in the heap.

Therefore:

Space Complexity: O(k)

Mistakes I Made While Working Through It

A few small mistakes helped make the heap behavior much clearer.

1. Checking the Wrong Heap Size

At first, I thought about:

len(min_k) <= k

But that is exactly when we want to keep the elements.

We only remove something when the heap becomes too large:

if len(min_k) > k:

2. Using heappop on an Element

I initially thought about something like:

heapq.heappop(min_k[-1])

But heappop() does not take an individual element.

It takes the entire heap:

heapq.heappop(min_k)

It automatically removes the smallest element.

3. Thinking the Minimum Might Be at the End

A heap is not a completely sorted list.

We should not assume:

min_k[-1]

has any special meaning.

For a min heap, the important guarantee is:

min_k[0]

is the smallest element.

The Main Pattern I Want to Remember

The biggest takeaway from this problem is not just how to solve LeetCode 215.

It is recognizing this pattern:

If I only care about the top k elements, I might not need to sort everything.

For the kth largest element:

Keep k largest elements
        ↓
Need to remove the smallest candidate
        ↓
Use a min heap
        ↓
Heap root becomes kth largest

So the one sentence I want to remember is:

Keep a min heap of the k largest elements seen so far. Whenever the heap grows beyond k, remove the smallest element. At the end, the smallest element in the heap is the kth largest element overall.