Kth Largest Element in an Array

How it works

Instead of sorting the whole array, we only need to keep track of the k largest elements seen so far.

A min-heap is perfect for this:

• A min-heap always keeps the smallest element at the top.
• If we maintain a heap of size k, then:
  • the heap will always contain the k largest elements seen so far.
  • the root of the heap (the smallest among these k) will be the k-th largest element.

Process:

• Add elements into the heap.
• If the heap grows larger than k, remove the smallest element.
• At the end, the root of the heap is exactly the k-th largest element.

This avoids sorting the entire array and keeps memory small.

Steps

1. Create an empty min-heap.
2. Iterate through each number:
   • Push the number into the min-heap.
   • If the heap size exceeds k, pop the smallest element.
3. After processing all numbers, the top of the heap is the k-th largest element.
4. Return that value.

Complexity

• Time complexity: O(n log k)
• Space complexity: O(k)

Where n is the length of the array nums.

Things to watch for

Confusing K-th Largest With K-th Smallest

The problem asks for the k-th largest element, not the k-th smallest. When using sorting, the k-th largest is at index n - k, not at index k - 1. Similarly, in QuickSelect, you must convert to the correct target index. Mixing up these indices is a very common source of off-by-one errors.

Using a Max-Heap Instead of a Min-Heap

For the heap approach, a min-heap of size k is the correct choice because it keeps the smallest of the k largest elements at the top. Using a max-heap would require storing all n elements and extracting k times, which is less efficient. The min-heap approach maintains O(k) space and O(n log k) time.

QuickSelect Worst Case on Sorted Arrays

QuickSelect degrades to O(n^2) time when the pivot choice is consistently poor, such as always picking the last element on an already sorted or reverse-sorted array. This can cause time limit exceeded errors. Using randomized pivot selection or median-of-three pivot selection helps avoid this worst case and keeps the average complexity at O(n).

import heapq

class Solution:
    def findKthLargest(self, nums, k):
        return heapq.nlargest(k, nums)[-1]

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        return minHeap.top();
    }
};