Kth Largest Element in an Array

Examples

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

Sorted descending: [6,5,4,3,2,1]. The 2nd entry is 5.

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

Sorted descending: [6,5,5,4,3,3,2,2,1]. The 4th entry is 4.

Constraints

• 1 <= k <= nums.length <= 10^4

• -10^4 <= nums[i] <= 10^4

Approach

Fully sorting the array (O(n log n)) is more work than the question asks for, since you only need one specific position in that sorted order, not the whole thing.

A min-heap of size k narrows this down: keep only the k largest values seen so far, and the top of the heap (the smallest among them) is the kth largest overall - the same idea used to track the kth largest element in a live stream.

Going further, quickselect (built on quicksort's partition step) can find the answer in average O(n) time: partition the array around a pivot so everything larger ends up on one side, and recurse into only the side that must contain the kth largest position - never both sides.

Solutions

Brute Force - Sort

Sort the array from largest to smallest, and read off the value at index k - 1.

function findKthLargest(nums, k) {
  const sorted = [...nums].sort((a, b) => b - a);
  return sorted[k - 1];
}

Time: O(n log n) · Space: O(n) for the sorted copy

Min-Heap of Size k

Push every number onto a min-heap, popping the smallest whenever the heap grows past size k. What's left on top at the end is the kth largest.

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  peek() {
    return this.data[0];
  }

  push(val) {
    this.data.push(val);
    let i = this.data.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.data[i] < this.data[parent]) {
        [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
        i = parent;
      } else break;
    }
  }

  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      const n = this.data.length;
      while (true) {
        let smallest = i;
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        if (left < n && this.data[left] < this.data[smallest]) smallest = left;
        if (right < n && this.data[right] < this.data[smallest]) smallest = right;
        if (smallest === i) break;
        [this.data[i], this.data[smallest]] = [this.data[smallest], this.data[i]];
        i = smallest;
      }
    }
    return top;
  }
}

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

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

Optimal (Average Case) - Quickselect

Reuse quicksort's partition step, but only recurse into the one side that must contain the target position - never both. On average this finds the answer in linear time.

function findKthLargest(nums, k) {
  const n = nums.length;
  const targetIndex = n - k; // index the answer would sit at if nums were sorted ascending

  function partition(left, right, pivotIndex) {
    const pivotValue = nums[pivotIndex];
    [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];
    let storeIndex = left;
    for (let i = left; i < right; i++) {
      if (nums[i] < pivotValue) {
        [nums[i], nums[storeIndex]] = [nums[storeIndex], nums[i]];
        storeIndex++;
      }
    }
    [nums[storeIndex], nums[right]] = [nums[right], nums[storeIndex]];
    return storeIndex;
  }

  function quickselect(left, right) {
    if (left === right) return nums[left];

    const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));
    const finalPivotIndex = partition(left, right, pivotIndex);

    if (finalPivotIndex === targetIndex) return nums[finalPivotIndex];
    if (finalPivotIndex < targetIndex) return quickselect(finalPivotIndex + 1, right);
    return quickselect(left, finalPivotIndex - 1);
  }

  return quickselect(0, n - 1);
}

Time: O(n) average case, O(n^2) worst case (mitigated in practice by the random pivot) · Space: O(1) extra (partitions in place), O(log n) average recursion depth