9.1 Find k-th Largest Element in an Array

9.1.1 Problem Metadata

9.1.2 Description

Given an unsorted array nums and an integer k, return the k-th largest element in the array. The k-th largest element is the element that would appear at index n - k after sorting the array in ascending order.

9.1.3 Examples

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

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

9.1.4 Constraints

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

9.1.5 Solution - Size-k Min Heap

9.1.5.1 Walkthrough

Maintain a min heap that keeps track of the current k largest elements seen so far. Iterate over nums, pushing each number into the heap and immediately popping whenever the heap size exceeds k. After processing all numbers, the heap root is the k-th largest element because every larger value is still inside the heap.

9.1.5.2 Analysis

  • Time Complexity: O(n log k) because each insertion and possible removal costs log k
  • Space Complexity: O(k) for the heap

9.1.5.3 Implementation Steps

  1. Initialize an empty min heap.
  2. For each num in nums, push it into the heap.
  3. If the heap size exceeds k, pop the smallest element.
  4. After processing, return the heap root.

9.1.5.4 Code - Java

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    return minHeap.peek();
}