Find Kth Largest Element in Array

215.Kth Largest Element in an Array

Heap

Array

Problem Statement:

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example:

Input:

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

→

Output:

5

Sorted array is [6,5,4,3,2,1], and the 2nd largest element is 5.

Algorithm:

1. Create a min heap to maintain k largest elements
2. Add each number to the heap
3. If heap size exceeds k, remove smallest element
4. Return top of heap (kth largest element)

public int findKthLargest(int[] nums, int k) {
    // Step 1: Create min heap (smallest element at top)
    PriorityQueue<Integer> pq = new PriorityQueue();

    // Step 2: Process each number in array
    for (int num : nums) {
        // Add current number to heap
        pq.add(num);
        // Step 3: Keep heap size as k, remove smaller elements
        while (pq.size() > k) pq.poll();
    }

    // Step 4: Top of min heap is kth largest element
    return pq.peek();
}

Complexity:

Time: O(n log k) | Space: O(k)