Kth largest Element in an Array

Problem Link

Kth Largest Element in an Array – LeetCode

Problem: Kth Largest Element in an 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 sorted order, not the kth distinct element.

Examples

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

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

Constraints

• 1 <= k <= nums.length <= 10⁵

• -10⁴ <= nums[i] <= 10⁴

Intuition

We want to find the kth largest element in the array. A brute-force approach would involve sorting the array in descending order and picking the kth element, which takes O(n log n) time. However, a more efficient way is to maintain a min-heap (priority queue) of size k. The top of the heap will always store the kth largest element.

Approach

1. Use a min-heap (Java's PriorityQueue) to store the top k largest elements seen so far.

2. Iterate through each number in the array:

   • Add the number to the heap.

   • If the heap size exceeds k, remove the smallest element (poll the root).

3. After the loop, the top of the heap (peek()) is the kth largest element.

Code (Java)

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i : nums){
            pq.add(i);
            if(pq.size() > k){
                pq.poll();
            }
        }
        return pq.peek();
    }
}

Time and Space Complexity

• Time Complexity: O(n log k)
  Each insertion and deletion from the heap takes O(log k), and we process n elements.

• Space Complexity: O(k)
  The heap stores at most k elements at any time.

Dry Run

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

• Initialize min-heap: []

• Add 3 → heap = [3]

• Add 2 → heap = [2, 3]

• Add 1 → size > 2 → remove 1 → heap = [3, 2]

• Add 5 → size > 2 → remove 2 → heap = [3, 5]

• Add 6 → size > 2 → remove 3 → heap = [5, 6]

• Add 4 → size > 2 → remove 4 → heap = [5, 6]

Top of the heap is 5 → 2nd largest

Conclusion

This is a classic heap-based selection problem that optimizes performance compared to sorting. By maintaining a min-heap of size k, we ensure that the kth largest element remains at the top, making retrieval efficient.