Kth Largest Element in an Array

Problem Statement

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

Note this is the kth largest in sorted order, not the kth distinct value.

Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Why:    sorted descending → [6, 5, 4, 3, 2, 1], the 2nd is 5

Input:  nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
Why:    duplicates count — sorted descending → [6, 5, 5, 4, ...], the 4th is 4

Intuition

The obvious solution is one line: sort descending, take index k - 1. That is O(n log n) and it is genuinely fine for most inputs.

But look at what it wastes. If n = 1,000,000 and k = 5, sorting carefully arranges all million values — and then you read five of them. The order of the other 999,995 was never needed.

Why a min-heap, when we want the largest?

This is the part that feels backwards, so it is worth slowing down.

Your container holds the current top k. When a new number arrives, you must answer one question: does this newcomer deserve a place?

It deserves a place if it beats the weakest member of your current top k. And the weakest member of the top k is the smallest of them.

So the value you need instant access to is the minimum — which is exactly what a min-heap gives you.

The real-world version

Imagine judging a competition and you only care about the top 3. You do not rank all 500 entries. You keep three slots on your desk. Each new entry is compared against the worst of the three you are holding. If it beats it, it takes its place and the loser is thrown out.

At the end, the worst of your three is the 3rd best overall.

Approach

Watch it run

Solution

import heapq


def find_kth_largest(nums: list[int], k: int) -> int:
    """Return the kth largest value using a min-heap of size k."""
    heap: list[int] = []

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

        # Keep only the k best. The popped value is the current weakest.
        if len(heap) > k:
            heapq.heappop(heap)

    # The root of a min-heap holding the top k is the kth largest.
    return heap[0]


def find_kth_largest_shortest(nums: list[int], k: int) -> int:
    """The one-liner, for when clarity matters more than the constant factor."""
    return heapq.nlargest(k, nums)[-1]

Complexity Analysis

• Time — one pass over n values, and each push or pop costs O(log k) because the heap never exceeds k items. When k is small this is very close to O(n).
• Space — the heap holds at most k values, no matter how large n is. This is the real prize: it lets you handle a stream of numbers too large to hold in memory.

Compared with sorting

Edge Cases

Related Problems

• Top K Frequent Elements — the same size-k idea, applied to counts instead of values
• Merge k Sorted Lists — a heap where the items are list heads
• Heaps — how sift-up and sift-down actually work