Kth Largest Element

Problem Statement

Given an unsorted array of integers nums and an integer k, return the K-th largest element. Note: this is the K-th in sorted order, not the K-th distinct element.

Input

An integer array nums and an integer k with 1 ≤ k ≤ nums.length.

nums = [3, 2, 1, 5, 6, 4]
k    = 2

Output

The K-th largest value — a single integer.

5
 
// sorted desc: [6, 5, 4, 3, 2, 1]
// 2nd largest → 5

Constraints

• 1 ≤ k ≤ nums.length ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴

Intuition

We only care about the top K elements seen so far. Maintain a min-heap sized to exactly K. As we stream in numbers, the root of the heap is always the smallest of the current top K. When a new number arrives bigger than the root, it deserves a spot in the top K — pop the root, push the new number. After processing everything, the root is the K-th largest.

step  x   heap (after)   note
 1    3   [3]            push
 2    2   [2,3]          push (size == k)
 3    1   [2,3]          push then pop → 1 evicted
 4    5   [3,5]          push then pop → 2 evicted
 5    6   [5,6]          push then pop → 3 evicted
 6    4   [5,6]          push then pop → 4 evicted
            ^root = 5 = 2nd largest ✓

Solution

import heapq
 
def findKthLargest(nums: list[int], k: int) -> int:
    min_heap: list[int] = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)      # evict the smallest
    return min_heap[0]                   # root == k-th largest

function findKthLargest(nums: number[], k: number): number {
  const h = minHeap<number>();
  for (const num of nums) {
    h.push(num);
    if (h.size > k) h.pop();             // evict the smallest
  }
  return h.peek()!;                       // root == k-th largest
}

Complexity

Edge Case Thinking