Kth Largest Element in an Array

MediumArray Heap Sorting

A monitoring system guards against sensor glitches: instead of alerting on the single highest reading in a batch, it alerts on the k-th highest, so that up to k - 1 freak spikes are ignored.

Given the batch nums and the integer k, return the k-th largest value: the value that would sit at position k, counting from 1, if nums were sorted from highest to lowest. Equal readings each take their own position, so in [9,9,4] both the first and the second largest are 9.

Sorting the whole batch works, but can you do better?

Example 1

Input: nums = [12,40,7,33,25], k = 2
Output: 33

Explanation: From highest to lowest: 40, 33, 25, 12, 7. The second value is 33.

Example 2

Input: nums = [5,8,8,3,8,1], k = 3
Output: 8

Explanation: The three 8s fill the top three positions.

Example 3

Input: nums = [-4,-11], k = 2
Output: -11

Explanation: Readings can be negative; the second largest of two readings is the smaller one.

Constraints

nums holds between 1 and 10^5 readings, and k is between 1 and that count.
Each reading fits in a 32-bit signed integer.

💡 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