Kth Largest Element in an Array

MediumHeap & Priority QueueArrayHeapQuickselectSorting

Problem

Given an unsorted array of integers and an integer k, find the kth largest value in the array when the values are considered in sorted order (not the kth distinct value), so duplicates count separately.

Example. For the array [3, 2, 1, 5, 6, 4] with k = 2, the sorted order is [1, 2, 3, 4, 5, 6], and the second largest is 5.

Key idea

Fully sorting the array answers the question but does more work than necessary, since only one position in the sorted order is needed, not the entire ordering. Two approaches exploit this in different ways.

The heap approach maintains a min-heap capped at size k of the largest values seen so far, exactly like the streaming version of this problem; after scanning the array, the top of the heap is the kth largest, at a cost of O(n log k). The quickselect approach adapts quicksort's partitioning: pick a pivot, partition the array so everything larger lands on one side and everything smaller on the other, then compare the pivot's resulting position to k. If the pivot landed exactly at the kth-largest position, it is the answer; otherwise recurse into only the side that must contain the answer, discarding the other entirely. Because only one side is ever explored, the expected work shrinks geometrically each round rather than repeating a full pass.

Solution

function findKthLargest(nums: number[], k: number): number {
  const targetIndex = nums.length - k; // kth largest sits at index (n - k) in ascending order

  const swap = (i: number, j: number): void => {
    [nums[i], nums[j]] = [nums[j], nums[i]];
  };

  const partition = (left: number, right: number): number => {
    const pivotIndex = left + Math.floor(Math.random() * (right - left + 1)); // random pivot avoids worst-case input patterns
    const pivotValue = nums[pivotIndex];
    swap(pivotIndex, right);

    let boundary = left;
    for (let i = left; i < right; i++) {
      if (nums[i] < pivotValue) {
        swap(i, boundary);
        boundary++;
      }
    }
    swap(boundary, right); // pivot lands at its final sorted position
    return boundary;
  };

  let left = 0;
  let right = nums.length - 1;
  while (true) {
    const pivotFinal = partition(left, right);
    if (pivotFinal === targetIndex) {
      return nums[pivotFinal];
    } else if (pivotFinal < targetIndex) {
      left = pivotFinal + 1; // answer is to the right, discard the left side
    } else {
      right = pivotFinal - 1; // answer is to the left, discard the right side
    }
  }
}

Complexity

  • Time: Heap approach O(n log k); quickselect averages O(n) but degrades to O(n²) in the worst case with poor pivot choices, which random pivot selection makes unlikely in practice.
  • Space: Heap approach O(k); quickselect O(1) extra with in-place partitioning (O(log n) recursion stack on average).

Watch out for

  • Quickselect's worst case comes from consistently unlucky pivots, such as always picking the first element on already-sorted input; a random pivot avoids this in practice.
  • Duplicates are counted by position in sorted order, not collapsed, so do not deduplicate before searching.

Pattern

This is the classic quickselect-versus-heap tradeoff for order-statistics problems: quickselect wins on average when the whole array is available up front, while a bounded heap fits better when data arrives as a stream.

Related questions