Kth Largest Element in an Array LeetCode Solution (2026)

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.

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

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

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();
}

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();
}

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

Algorithmic Pattern

Master the Heap / Priority Queue Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Heap / Priority Queue pattern.

Framework: Heap / Priority Queue • Interview Prep: Tested at FAANG • Explore all Heap / Priority Queue problems & invariants →

How to Recognize This Pattern

Find kth largest/smallest
Streaming data

Complexity Analysis

Time Complexity

O(n log k)

Space Complexity

O(k)

Frequently Asked Questions

What is the optimal time and space complexity for Kth Largest Element in an Array?

The optimal solution for Kth Largest Element in an Array achieves O(n log k) runtime complexity and requires O(k) auxiliary space. 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.

How do I identify that Kth Largest Element in an Array requires the Heap / Priority Queue pattern?

In technical interviews, look for key problem signals: Find kth largest/smallest; Streaming data. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Heap / Priority Queue strategy.

What critical edge cases must be handled in Kth Largest Element in an Array?

Essential edge cases to verify include: 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. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Kth Largest Element in an Array?

Kth Largest Element in an Array is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Facebook, Amazon, Apple, Google.

Kth Largest Element in an Array LeetCode Solution