Kth Largest Element in an Array

Approach Summary

Maintain a min-heap of size k. Each new element replaces the min if it is larger. The heap top is the kth largest.

Full Solution & Approach

Maintain a min-heap of size k. Iterate through the array, push each element, and whenever the heap exceeds size k, pop the smallest. After the pass the heap contains exactly the k largest elements, and its root — the minimum of those k — is the k-th largest overall. The heap stays at size k, so every push/pop is O(log k) and the total is O(n log k). This beats sorting (O(n log n)) when k is small relative to n and is the standard streaming-friendly answer. The alternative, Quickselect, gives expected O(n) but has a worst case of O(n²) and is harder to get right; the heap is the safe interview answer. In Python, heapq is a min-heap directly. In JavaScript you either build a small heap class (shown) or use the bucket approach.

Each of the n elements does one heap operation costing O(log k) — O(n log k) time. The heap holds exactly k elements — O(k) space.

Solution Code

Solution

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:
    heap = nums[:k]
    heapq.heapify(heap)
    for n in nums[k:]:
        if n > heap[0]:
            heapq.heapreplace(heap, n)
    return heap[0]

class MinHeap {
  constructor() { this.arr = []; }
  size() { return this.arr.length; }
  peek() { return this.arr[0]; }
  push(v) {
    this.arr.push(v);
    let i = this.arr.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.arr[p] <= this.arr[i]) break;
      [this.arr[p], this.arr[i]] = [this.arr[i], this.arr[p]];
      i = p;
    }
  }
  pop() {
    const top = this.arr[0];
    const last = this.arr.pop();
    if (this.arr.length) {
      this.arr[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let s = i;
        if (l < this.arr.length && this.arr[l] < this.arr[s]) s = l;
        if (r < this.arr.length && this.arr[r] < this.arr[s]) s = r;
        if (s === i) break;
        [this.arr[i], this.arr[s]] = [this.arr[s], this.arr[i]];
        i = s;
      }
    }
    return top;
  }
}

function findKthLargest(nums, k) {
  const heap = new MinHeap();
  for (const n of nums) {
    heap.push(n);
    if (heap.size() > k) heap.pop();
  }
  return heap.peek();
}

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int n : nums) {
        heap.offer(n);
        if (heap.size() > k) heap.poll();
    }
    return heap.peek();
}

int findKthLargest(const vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int n : nums) {
        heap.push(n);
        if ((int)heap.size() > k) heap.pop();
    }
    return heap.top();
}

Edge Cases to Watch

k = 1 — the largest element
k = n — the smallest element
Duplicate values — they occupy separate heap slots and are counted correctly
All elements identical — any of them is the answer

How to Recognize This Pattern

Find kth largest/smallest
Streaming data

Complexity Analysis

Time Complexity

O(n log k)

Space Complexity

O(k)