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 quick-select

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. Quick select partitions until index n-k is the pivot.

Approaches

Min-heap of size k

Unverified

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). Prefer the heap when k is tiny or the array must stay intact.

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]!;
}

Quick select

Unverified

Time O(n) averageSpace O(1)

Idea. The kth largest is the element at index n-k in sorted order. Randomized partition until the pivot lands there; loop into only one side. Mutates the array in place.

Walkthrough. [3,2,1,5,6,4], k=2 → target index 4. After partitions the value at index 4 is 5.

Trade-offs. Average O(n), worst O(n²) without a random pivot. The Quick Select default. k is 1-indexed.

Solution

export function findKthLargest(nums: number[], k: number): number {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

export function findKthLargest(nums: number[], k: number): number {
  const target = nums.length - k;
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const p = partition(nums, lo, hi);
    if (p === target) return nums[p]!;
    if (p < target) lo = p + 1;
    else hi = p - 1;
  }
  return nums[lo]!;
}

function partition(nums: number[], lo: number, hi: number): number {
  const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
  [nums[rand], nums[hi]] = [nums[hi]!, nums[rand]!];
  const pivot = nums[hi]!;
  let i = lo;
  for (let j = lo; j < hi; j++) {
    if (nums[j]! < pivot) {
      [nums[i], nums[j]] = [nums[j]!, nums[i]!];
      i++;
    }
  }
  [nums[i], nums[hi]] = [nums[hi]!, nums[i]!];
  return i;
}

Template connection

Heap top-K, or Quick Select to rank n-k. Flagship kth-largest problem for both patterns.

Reflection

The top of a min-heap of size k is the kth largest. Push every value and pop once the size passes k. Quickselect is linear on average.
k == n is the smallest value. k == 1 is the largest. Duplicates are distinct elements. Do not unique them.
A bad pivot makes quickselect quadratic. The heap stays O(n log k).