42. Kth Largest Element in an Array · DSA Practice

Return the k-th largest element in nums (in sorted order, not the k-th distinct value). Can you avoid sorting the whole array?

Example 1

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

Output: 5

Example 2

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

Output: 4

Hint 1

Keep only the k largest values seen so far in a min-heap.

Hint 2

The heap’s top is then the k-th largest.

HeapQuickselect

Approach 1: Sort

Sort descending and index k−1.

⏱ Time O(n log n)💾 Space O(1)

Approach 2: Min-heap of size k

Push each value; pop when size exceeds k.

⏱ Time O(n log k)💾 Space O(k)

Approach 3: Quickselect ✅

Partition like quicksort but recurse into one side only.

⏱ Time O(n) average💾 Space O(1)

Reference solution for Quickselect (time O(n) average, space O(1)). Each solution passes every test in all four languages.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []                      # min-heap of the k largest values seen
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)    # drop the smallest
        return heap[0]                 # smallest of the k largest

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap of k largest
        for (int x : nums) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();
        }
        return heap.peek();
    }
}

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;   // min-heap of k largest
        for (int x : nums) {
            heap.push(x);
            if ((int)heap.size() > k) heap.pop();
        }
        return heap.top();
    }
};

class MinHeap {
  constructor(less = (a, b) => a < b) { this.a = []; this.less = less; }
  get size() { return this.a.length; }
  peek() { return this.a[0]; }
  push(x) { const a = this.a; a.push(x); let i = a.length - 1;
    while (i > 0) { const p = (i - 1) >> 1; if (!this.less(a[i], a[p])) break; [a[i], a[p]] = [a[p], a[i]]; i = p; } }
  pop() { const a = this.a, top = a[0], last = a.pop();
    if (a.length) { a[0] = last; let i = 0;
      while (true) { const l = 2 * i + 1, r = l + 1; let m = i;
        if (l < a.length && this.less(a[l], a[m])) m = l;
        if (r < a.length && this.less(a[r], a[m])) m = r;
        if (m === i) break; [a[i], a[m]] = [a[m], a[i]]; i = m; } }
    return top; }
}

function findKthLargest(nums, k) {
  const heap = new MinHeap(); // min-heap of the k largest
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop();
  }
  return heap.peek();
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Heaps & Priority Queues.