48. Kth Largest Element in an Array

MediumArray Heap Sorting

Given an integer array nums and an integer k, return the k-th largest element: the value that would be at position k (1-indexed) if the array were sorted in descending order.

Duplicates count separately. In [4,4,1], both the 1st and 2nd largest are 4.

Can you beat sorting the whole array?

Example 1

Input: nums = [7,1,5,3,9], k = 2
Output: 7

Explanation: Sorted descending: 9, 7, 5, 3, 1. The second value is 7.

Example 2

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

Explanation: Sorted descending: 4, 4, 4, 2, 1. Repeated values each take a position.

Example 3

Input: nums = [-3], k = 1
Output: -3

Constraints

1 <= k <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1

💡 Hint 1

Sorting gives an easy O(n log n) answer. Do you really need the whole array in order?

💡 Hint 2

Keep a min-heap of the k largest values seen so far. When it grows past k, pop the smallest. The heap top is the answer at the end: O(n log k).

💡 Hint 3

Quickselect partitions around a pivot like quicksort, but only continues into the side that contains the target index. With a random pivot this averages O(n).

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

The k-th largest sits at index n - k of the ascending order, so find that order statistic with quickselect. Pick a random pivot and do a three-way partition of the current range into < pivot, == pivot and > pivot. If the target index falls in the middle block, the pivot is the answer; otherwise keep only the side that contains the target and repeat. The random pivot makes the expected work O(n), and the three-way split keeps arrays full of duplicates fast. A size-k min-heap (keep the k largest seen, the top is the answer) is the simpler O(n log k) alternative.

Time O(n) on average (O(n²) worst case); the heap version is O(n log k)Space O(1) extra (the array is rearranged in place)

function findKthLargest(nums, k) {
  const target = nums.length - k;
  const swap = (a, b) => {
    const t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
  };
  let lo = 0;
  let hi = nums.length - 1;
  while (true) {
    const pivot = nums[lo + Math.floor(Math.random() * (hi - lo + 1))];
    let lt = lo, i = lo, gt = hi;
    while (i <= gt) {
      if (nums[i] < pivot) swap(lt++, i++);
      else if (nums[i] > pivot) swap(i, gt--);
      else i++;
    }
    if (target < lt) hi = lt - 1;
    else if (target > gt) lo = gt + 1;
    else return pivot;
  }
}

class Solution {
    private final Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        int target = nums.length - k;
        int lo = 0, hi = nums.length - 1;
        while (true) {
            int pivot = nums[lo + random.nextInt(hi - lo + 1)];
            int lt = lo, i = lo, gt = hi;
            while (i <= gt) {
                if (nums[i] < pivot) swap(nums, lt++, i++);
                else if (nums[i] > pivot) swap(nums, i, gt--);
                else i++;
            }
            if (target < lt) hi = lt - 1;
            else if (target > gt) lo = gt + 1;
            else return pivot;
        }
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function findKthLargest(nums, k) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit