← Back to Index

📚 Kth Largest Element in an Array – Java Cheat Sheet

📌 What Is It?

The Kth Largest Element in an Array problem involves finding the Kth largest element in an unsorted array. This is commonly solved using a min-heap or the Quickselect algorithm.

🧱 Pattern Template

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Step 1: Add elements to the heap
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the smallest element
            }
        }

        // Step 2: The root of the heap is the Kth largest element
        return minHeap.peek();
    }
}

📊 Time Complexity

• Heap Operations: O(N log K) – Adding and removing elements from the heap.
• Overall Complexity: O(N log K).

✅ Use Cases

• Finding the Kth largest or smallest element in an array
• Efficiently processing large datasets
• Applications in ranking and leaderboard systems

📘 Common LeetCode Problems

• 215. Kth Largest Element in an Array [Medium] Heap
• 378. Kth Smallest Element in a Sorted Matrix [Medium] Heap

🧪 Example: Kth Largest Element in an Array

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

Explanation:
- Add elements to the heap and maintain its size as K.
- The 2nd largest element is 5.

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the K largest elements.
• Edge cases: empty arrays, K greater than the array size.
• Consider Quickselect for better performance when K is large.