#215 - Kth Largest Element in an Array

MediumHeap / Priority Queue

Given an integer array nums and an integer k, return the k-th largest element. Note that it is the k-th largest in sorted order, not the k-th distinct element.

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

Solution Space

Try it

/**
 * Finds the k-th largest element using a min-heap of size k.
 * After processing all elements, the heap top is the k-th largest.
 *
 * @param nums Array of integers
 * @param k    1-based rank from largest
 * @returns    The k-th largest value
 */
export function findKthLargest(nums: number[], k: number): number {
  // Min-heap of size k (using a sorted array for simplicity)
  const heap: number[] = [];

  for (const num of nums) {
    heap.push(num);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift(); // remove smallest
  }

  return heap[0];
}

Approach: min-heap of size k – maintain a heap of the k largest elements seen so far. After processing all elements, the root is the k-th largest.

Time: O(n log k) with a proper heap – each insertion/extraction is O(log k).

Space: O(k) – the heap stores at most k elements.

Alternative approaches:

Approach	Idea	Time	Space
Quickselect	Partition like quicksort, recurse only into the half containing the k-th element	O(n) average, O(n²) worst	O(1)
Full sort	Sort the array and return nums[n - k]	O(n log n)	O(1) or O(n)

Why the min-heap method is preferred: guarantees O(n log k) time, which beats O(n log n) sorting when k ≪ n. Quickselect is faster on average but has poor worst-case guarantees without randomization.

#1926 Nearest Exit from Entrance in Maze

#2336 Smallest Number in Infinite Set