Kth Largest Element

You'll keep only the k largest values in a min-heap, so the answer is always at the top. You need Python's heapq. Related chapter: heaps.

1. The problem

You get a list of integers and a number k. Return the kth largest value, counting repeats separately. Numbers can be negative, and 1 ≤ k ≤ n. Don't change the input. LeetCode 215.

"Counting repeats separately" is the phrase that matters. In [5,5,4], the second largest is 5, not 4.

2. A correct baseline

def baseline(nums,k):
    return sorted(nums,reverse=True)[k-1]

assert baseline([3,2,1,5,6,4],2)==5
assert baseline([5,5,4],2)==5
assert baseline([-2],1)==-2

Sorting takes O(n log n) time and O(n) space for the sorted copy. On a million numbers, that's about 20 million comparisons.

The bottleneck. It puts every number in order, but only the k largest can affect the answer.

3. The observation

Take [3,2,1,5,6,4] with k=2. Keep the two largest values so far. After 3 and 2, you hold {2, 3}. When 5 arrives, it beats the smaller one, 2, so 2 goes. Each new number only has to beat the smallest value you're holding.

A min-heap keeps its smallest value at the top, so that check takes one look. When a new number is bigger, swap it in for the top. At the end, the top of the heap is the smallest of the k largest: the kth largest. A max-heap would put the wrong end on top.

4. The solution and a trace

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        """Requires 1 <= k <= len(nums); duplicates count separately."""
        best=nums[:k]
        heapq.heapify(best)
        for i in range(k,len(nums)):
            if nums[i]>best[0]:
                heapq.heapreplace(best,nums[i])
        return best[0]

solve=Solution().findKthLargest
assert solve([3,2,1,5,6,4],2)==5
assert solve([5,5,4],2)==5
assert solve([-2],1)==-2

Trace [3,2,1,5,6,4] with k=2. The sets show the values held, not how the heap stores them:

5. Why it works

What stays true. The heap holds the k largest values seen so far.

Why each step keeps it true. A number no bigger than the top can't be among the k largest, so we skip it. A bigger number pushes out the smallest held value, the only one it beats.

The answer is right. At the end, the heap holds the k largest values. Its smallest, the top, is the kth largest.

6. Cost, edge cases, and failure

Cost. Building the heap takes O(k) time. Each later number may cost one O(log k) swap, so the total is O(n log k) time. With k = 10 and a million numbers, that's about 3 million steps instead of 20 million. The heap takes O(k) space.

Edge cases. k = 1 finds the maximum. k = n finds the minimum.

Where it fails. Only the top of a heap is in order; the rest isn't sorted. So putting every number in one min-heap gives you the minimum, not the kth largest:

import heapq
wrong=[3,6,5]
heapq.heapify(wrong)
assert wrong[0]==3 and baseline(wrong,2)==5  # Whole-array min-heap root is not kth largest.

import random
rng=random.Random(215)
for _ in range(500):
    nums=[rng.randint(-10,10) for _ in range(rng.randint(1,30))]
    before=nums.copy(); k=rng.randint(1,len(nums))
    assert solve(nums,k)==baseline(nums,k)
    assert nums==before