Problem: Kth Largest Element in an Array

Problem Statement

Given an integer array nums and an integer k, return the k-th largest element in the array.

Note that it is the k-th largest element in the sorted order, not the k-th distinct element.

Approach: Min-Heap of Size K

Instead of sorting the whole array ($O(n \log n)$), we can use a Min-Heap to keep track of the $k$ largest elements seen so far.

1. Initialize: Create a Min-Heap.
2. Iterate:
   • Push each number into the heap.
   • If heap size exceeds $k$, pop the smallest element (heap.poll()).
3. Result: The smallest element in the heap of size $k$ is the $k$-th largest element in the array.

Java Implementation

public int findKthLargest(int[] nums, int k) {
    // Java's PriorityQueue is a Min-Heap by default
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // Remove the smallest of the K largest
        }
    }
    
    return minHeap.peek();
}

Complexity Analysis

• Time Complexity: $O(n \log k)$. Each of the $n$ elements is pushed into a heap of size $k$.
• Space Complexity: $O(k)$ to store the heap.

Interview Tips

• Mention that this is much more efficient than sorting when $k$ is much smaller than $n$.
• Be prepared to discuss QuickSelect, which can solve this in $O(n)$ average time. 埋