Kth Largest Element in an Array

Given an integer array nums and an integer k, return the value that would be at position k if the array were sorted from largest to smallest (counting from 1).

Duplicates count separately: in [5, 5, 1] the largest element is 5 and the second largest is also 5. Try to do better than sorting the whole array.

Example 1

Example 2

Example 3

Constraints

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

Pattern Path · Heaps & Top-K · problem 105 of 169

Start simple

Sort the array in descending order and return the element at index k - 1: O(n log n) time.

The key idea

Quickselect is quicksort that only follows the half containing the answer. Pick a random pivot and split the values into three groups: those greater than the pivot, those equal to it, and those smaller.

• If k is at most the size of the greater group, the answer is the k-th largest within that group.
• Otherwise, if k also fits within greater + equal, the answer is the pivot itself.
• Otherwise, the answer is in the smaller group, at rank k - |greater| - |equal|.

Each round discards at least one group without sorting it. A random pivot lands near the middle often enough that the remaining work shrinks geometrically: n + n/2 + n/4 + ... is about 2n, giving O(n) expected time. Splitting off the equal group is what keeps arrays full of duplicates from degrading to quadratic time.

A min-heap of size k is a solid alternative: push each value and pop whenever the heap exceeds k; the heap's top is then the answer, in O(n log k) time with O(k) memory, which also works on a stream.

Complexity

• Time: O(n) expected (O(n<sup>2</sup>) worst case)
• Space: O(n)

Python

import random

class Solution:
    def findKthLargest(self, nums, k):
        while True:
            pivot = random.choice(nums)
            larger = [x for x in nums if x > pivot]
            equal = sum(1 for x in nums if x == pivot)
            if k <= len(larger):
                nums = larger  # the answer is among the larger values
            elif k <= len(larger) + equal:
                return pivot  # the answer is the pivot itself
            else:
                k -= len(larger) + equal
                nums = [x for x in nums if x < pivot]

JavaScript

var findKthLargest = function(nums, k) {
  while (true) {
    const pivot = nums[Math.floor(Math.random() * nums.length)];
    const larger = [], smaller = [];
    let equal = 0;
    for (const x of nums) {
      if (x > pivot) larger.push(x);
      else if (x < pivot) smaller.push(x);
      else equal++;
    }
    if (k <= larger.length) {
      nums = larger; // the answer is among the larger values
    } else if (k <= larger.length + equal) {
      return pivot; // the answer is the pivot itself
    } else {
      k -= larger.length + equal;
      nums = smaller;
    }
  }
};

What the interviewer is checking

It is the canonical top-k question: the interviewer wants to hear the sort, heap and quickselect options with their trade-offs, and then see one implemented correctly.

Mistakes to avoid

• Removing duplicates first; the k-th largest counts repeated values separately.
• Using a max-heap of all n elements and popping k times, which is O(n + k log n) but misses the size-k heap insight.
• A fixed pivot (first or last element) that goes quadratic on sorted input or on many equal values.
• Off-by-one between the k-th largest (1-based) and index k - 1 or n - k.

Follow-ups to expect

• What if the numbers arrive as a stream? (Size-k min-heap.)
• Guarantee O(n) worst case. (Median-of-medians pivot.)
• Values lie in a small range. (Counting sort, O(n + range).)

In real software

Databases answer ORDER BY ... LIMIT k and percentile queries (such as p99 latency) with selection algorithms or bounded heaps instead of sorting every row.

Practice next