Kth Largest Element: Size-K Min-Heap Pattern

Learning Outcome

After this lesson, you should be able to use a min-heap as a fixed-size filter for the k largest values.

Problem Statement

Given an unsorted array and integer k, return the kth largest element.

Brute Force Approach

Sort the full array and read index n - k. This is simple but sorts more than needed.

Optimized Approach

Maintain a min-heap of size k. After every push, remove the smallest if the heap is too large, so the heap keeps the k largest values.

Exact Pseudocode

heap = empty min heap
for x in nums:
  push x into heap
  if heap size is greater than k:
    pop smallest
return heap top
  

Reference Code

import heapq

class Solution:
    def findKthLargest(self, nums, k):
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]
  

Sample Dry Run

Complexity

Edge Cases

• k = 1 returns the maximum value.
• Duplicates count as separate elements.
• k is assumed valid in the standard problem.

Interview Checklist

• Use a min-heap, not a max-heap, for size-k filtering.
• Pop only when heap size exceeds k.
• Return heap top after all numbers are processed.

FAQs

The heap stores the k largest values seen so far, so the smallest among them is the kth largest.

Sorting is fine but costs O(n log n), while the heap only pays log k per item.

Size-k min-heap.