LeetCode #215 Medium

Kth Largest Element in an Array

Return the k-th largest element (not distinct) without fully sorting.

heapquickselectarray

02

Intuition

💡

Keep a min-heap of the k largest seen so far — its root is always the current k-th largest. Anything smaller than the root can't matter; anything bigger evicts the root. n pushes into a size-k heap beats a full sort when k ≪ n.

03

Approach

1

Why a MIN-heap for largest

The gatekeeper of 'top k' is the smallest member of that club — exactly what a min-heap exposes at its root.

2

Stream the array through

Seed the heap with the first k values, then for each remaining value compare it against the root. If it is not larger, it cannot belong to the top k — skip it entirely. If it is larger, heapreplace swaps it in and sifts down in one step, evicting the old minimum. Invariant: the heap always holds the k largest elements seen so far.

3

Alternative: quickselect

Partition around a pivot and recurse into the side containing index n−k — O(n) average, O(n²) worst; the heap is the safe default.

04

Solution & live demo

python

▶1import heapq
▶2 
▶3class Solution:
▶4    def findKthLargest(self, nums, k):
▶5        heap = nums[:k]
▶6        heapq.heapify(heap)
▶7        for n in nums[k:]:
▶8            if n > heap[0]:
▶9                heapq.heapreplace(heap, n)
▶10            # else: n can't be in the top k
▶11        return heap[0]

05

Edge cases

k = n

Heap holds everything; root is the minimum — correct.

Duplicates around the boundary

'k-th largest' counts repeats; the heap does so naturally.

06

Complexity

Time

O(n log k)

Space

O(k)

Each of n elements costs one size-k heap op.