LeetCode 215 · Heap / Priority Queue

Kth Largest Element in an Array, explained with a picture

A podium that only keeps the top k.

MediumHeap / Priority Queue
▶ Watch it step by step

The problem

Find the k-th largest number in an unsorted list (k-th in sorted order, not the k-th distinct).

Input:  [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Picture it

Picture a podium with only k places, where the weakest of the k sits at the front. Every number tries to get on; if the podium is over-full, the weakest steps off. After everyone has tried, the weakest person still standing is exactly the k-th largest.

How to recognise it

  • You need one element by rank (the k-th largest) from an unsorted array.
  • You do not need the full sorted order, only the value sitting at one position of it.
  • "k-th" counts duplicates: in [3, 2, 3, 1, 2, 4, 5, 5, 6] with k = 4 the answer is 4, because the sorted order from the top is 6, 5, 5, 4.
  • n can reach 10^5, so repeated linear scans are out, and a hint like "can you do it without sorting?" points to a heap (a tree stored in a list that keeps its smallest item at index 0, with O(log n) push and pop) or to quickselect (a partial quicksort).

Start with brute force

Find the maximum and remove it, k − 1 times. The maximum of what is left is the answer.

def find_kth_largest_brute(nums, k):
    s = list(nums)
    for _ in range(k - 1):
        s.remove(max(s))       # scan to find it, scan again to remove it
    return max(s)

Each round scans the list twice, so time is O(n · k) and space is O(n) for the copy. For n = 10^5 and k = 5 × 10^4 that is about 5 × 10^9 steps, too slow. Sorting the whole array (O(n log n)) would pass the limits, but it orders far more than the question needs.

From brute force to the idea

  1. Find the waste. The brute force re-examines the entire list in every round, even though the same big numbers keep winning.
  2. Only the top k matter. The k-th largest is decided by the k largest numbers, and it is the smallest of them.
  3. Keep those k in a min-heap. Push each number. If the heap grows past k items, heappop removes its smallest, which cannot be among the top k.
  4. Read the front. After the last number, the heap holds exactly the k largest, and heap[0] is the smallest of them: the k-th largest.

This is the key idea: a min-heap that never grows beyond k items, with the answer at its front.

Quickselect can reach O(n) on average, but its worst case is O(n²) and it rearranges the input, so the heap is the safer first answer.

The key idea

Min-heap of size k: the top is the answer. O(n log k).

Python solution

def find_kth_largest(nums, k):
    heap = []                  # min-heap of the k largest so far
    for x in nums:
        heappush(heap, x)
        if len(heap) > k:
            heappop(heap)          # the weakest leaves
    return heap[0]

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (remove the max k − 1 times)O(n · k): two scans of the list per roundO(n): the copy
Min-heap of size k (shown code)O(n log k): each number does one push and at most one pop on a heap of at most k + 1 itemsO(k): the heap

Edge cases

  • k = 1: the heap keeps one number, the maximum.
  • k = n: nothing is popped, and the front is the minimum.
  • Duplicates ([3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4): returns 4, because equal values count separately.
  • All equal ([-1, -1], k = 2): returns -1.
  • Single element ([5], k = 1): returns 5.
  • k larger than n: not allowed by the problem. The code does not raise an error; find_kth_largest([1, 2], 3) returns 1, which is not a real 3rd largest.
  • Empty array: heap[0] raises IndexError.
  • Input is not changed. The code needs from heapq import heappush, heappop.

Common mistakes

  • Using a max-heap of all n numbers and popping k times. It works but costs O(n + k log n) time and O(n) space.
  • Counting distinct values by mistake. The problem asks for the k-th in sorted order, so duplicates stay.
  • Popping before pushing when the heap is full, which replaces the smallest even when the new number is smaller. On [4, 3, 2, 1] with k = 2 that returns 1 instead of 3.
  • Returning heap[k - 1]: a heap is not sorted, so only index 0 has a guaranteed meaning.
Your turn: sum of the top k

Return the sum of the k largest numbers in the array. Describe your approach, then write it if you like.

Compare with our answer

The same min-heap of size k now holds exactly the numbers you want. Instead of reading the front, add up the heap at the end.

from heapq import heappush, heappop

def sum_of_top_k(nums, k):
    heap = []
    for x in nums:
        heappush(heap, x)
        if len(heap) > k:
            heappop(heap)
    return sum(heap)

sum_of_top_k([3, 2, 1, 5, 6, 4], 2) is 11 (6 + 5). Time O(n log k) for the loop plus O(k) for the sum, space O(k).

A strong answer mentions: reusing the size-k min-heap, summing its contents (not just the front), and the O(n log k) cost.

Check what stuck

1. You must report the 100 highest scores from a log of 50 million entries, and memory is tight. Which approach fits best?

2. Why does a min-heap, not a max-heap, give the k-th largest in the shown solution?

3. A learner pops first when the heap is full, then pushes (if len(heap) >= k: heappop(heap) before heappush). Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.