Leetcode 215. Kth Largest Element in an Array

Let's understand what we're being asked to do. We have an unsorted array like [3, 2, 1, 5, 6, 4] and need to find the k-th largest element. For k=2, we want the 2nd largest element.

If we sorted the array: [1, 2, 3, 4, 5, 6], the 2nd largest would be 5 (at index length-2 from the end). But the problem says we should solve it faster than full sorting for large inputs.

Important constraint: We're looking for the k-th largest by sorted order, not distinct values. So if the array is [3, 2, 3, 1, 2, 4, 5, 5, 6] and k=4, the answer is 4 (the 4th element from the end when sorted: [1,2,2,3,3,4,5,5,6]).

Edge cases to consider: What if k=1 (largest element)? What if k equals the array length (smallest element)? What if the array has duplicates?

The most straightforward approach is to sort the entire array in descending order, then return the element at index k-1. This guarantees we find the k-th largest element but requires sorting all elements even though we only need one value. For small arrays this is simple and effective, but for large inputs (~10^5 elements) we can do better by avoiding the full sort.

def find_kth_largest(nums, k):
    """
    Brute force: Sort entire array in descending order,
    then return element at index k-1.
    Time: O(n log n), Space: O(1) or O(n) depending on sort.
    """
    # Sort the entire array in descending order
    nums.sort(reverse=True)
    
    # Return the k-th largest element (index k-1)
    return nums[k - 1]

We don't actually need the entire array sorted - we only care about finding the k-th largest element's position.

If we pick a pivot element and partition the array around it (smaller elements on left, larger on right), we know the pivot's final sorted position. If that position is exactly where the k-th largest should be, we're done!

By partitioning around a pivot, we can eliminate half the array from consideration. If the k-th largest is in the right partition, we don't need to look at the left partition at all.

This transforms an O(n log n) sorting problem into an average O(n) selection problem - we're doing less work because we're asking a simpler question.

Think about finding the tallest person in a room. You don't need to line everyone up by height (sorting). Instead, you could:

1. Pick someone at random as a reference
2. Split the room: taller people on the right, shorter on the left
3. Count how many are on the right - if it's exactly k-1, your reference person is the k-th tallest!
4. If more than k-1 are taller, repeat the process on the right side only
5. If fewer than k-1 are taller, repeat on the left side

This divide and conquer approach eliminates large portions of the search space with each step.

The optimal approach uses a min-heap of size k to track the k largest elements seen so far. Iterate through the array: for each element, if the heap has fewer than k elements, add it; otherwise, if the element is larger than the heap's minimum (top), remove the minimum and add the new element. After processing all elements, the heap's minimum is the k-th largest element. This approach is faster than full sorting because we only maintain k elements in the heap, and heap operations are logarithmic in k, not n.

import heapq
def find_kth_largest(nums, k):
    """
    Find k-th largest element using min-heap of size k.
    Time: O(n log k), Space: O(k)
    """
    # Initialize min-heap to track k largest elements
    min_heap = []
    
    # Process each element in array
    for num in nums:
        # If heap has fewer than k elements, add current element
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        # If current element is larger than heap minimum, replace it
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)
    
    # The root of min-heap is the k-th largest element
    return min_heap[0]

• Min-heap for top-K problems: When finding the k-th largest element, maintain a min-heap of size k - the root is always the k-th largest because smaller elements get evicted. This inverts intuition (min-heap for largest) but ensures O(n log k) efficiency by keeping the heap bounded.
• Heap size maintenance pattern: The critical technique is adding elements then popping when size exceeds k - this ensures the heap contains exactly the k largest elements seen so far. Always check `heap.size() > k` after insertion, not before, to handle the initial k elements correctly.
• Quickselect vs Heap tradeoff: Quickselect offers O(n) average time but O(n²) worst case and requires array modification, while heap guarantees O(n log k) with no modification and works on streams. Choose heap when k is small relative to n (k << n) or when data arrives incrementally.
• K-th largest vs smallest confusion: A common mistake is using max-heap for k-th largest - remember that min-heap tracks largest elements (small values get removed) and max-heap tracks smallest elements (large values get removed). The heap type is opposite to what you're finding.
• Space-time optimization insight: The heap approach uses O(k) space instead of O(n), making it superior when k is much smaller than n. For k = n/2 or larger, full sorting at O(n log n) may be more practical than O(n log k) since log k approaches log n.
• Streaming data pattern: This heap technique extends to real-time top-K monitoring (trending items, leaderboards, anomaly detection) where you can't store all data. Each new element is processed in O(log k) time, making it perfect for continuous data streams or memory-constrained environments.