Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumheap-top-k

Kth Largest Element in an Array

Problem (restated)

Find the kth largest element in an unsorted array (not distinct required).

Intuition

Min-heap of size k holds the largest k seen; root is kth largest.

Approaches

Min-heap of size k

Tested only

Time O(n log k)Space O(k)

Idea. Push all; pop when size>k; return peek.

Walkthrough. [3,2,1,5,6,4], k=2 → 5.

Trade-offs. Heap O(n log k) vs quickselect average O(n).

Solution

export function findKthLargest(nums: number[], k: number): number {
  // min-heap via sorted insert on small k (simple, correct)
  const heap: number[] = [];
  const push = (x: number) => {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  };
  for (const x of nums) push(x);
  return heap[0]!;
}

export function findKthLargest(nums: number[], k: number): number {
  // min-heap via sorted insert on small k (simple, correct)
  const heap: number[] = [];
  const push = (x: number) => {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  };
  for (const x of nums) push(x);
  return heap[0]!;
}

Template connection

Heap top-K.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?