Kth Largest Element | Heaps

Problem Statement

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

Note:

Not the kth distinct element.

---

Brute Force Intuition

In an interview, you can explain it like this:

Sort the entire array in descending order and return the kth element.

Complexity

• Time Complexity: O(N log N)
• Space Complexity: O(1)

Brute Force Code

Arrays.sort(nums);

return nums[nums.length - k];

---

Moving Towards the Better Heap Approach

Do we really need the entire sorted array?

No.

We only care about:

Top K largest elements

A Min Heap of size K is sufficient.

---

Pattern Recognition

Whenever you see:

• Kth Largest
• Kth Smallest
• Top K Elements

Think:

Heap

---

Better Approach

Maintain a Min Heap.

For every element:

pq.add(num);

If heap size exceeds:

k

remove smallest.

pq.poll();

At the end:

Top of heap
=
Kth Largest Element

---

Optimal Java Solution

class Solution {

    public int findKthLargest(int[] nums, int k) {

        PriorityQueue<Integer> pq =
            new PriorityQueue<>();

        for (int num : nums) {

            pq.add(num);

            if (pq.size() > k) {
                pq.poll();
            }
        }

        return pq.peek();
    }
}

---

Dry Run

Input

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

k = 2

Heap:

3

2 3

1 2 3
remove 1

2 3

2 3 5
remove 2

3 5

3 5 6
remove 3

5 6

4 5 6
remove 4

5 6

Answer:

5

---

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log K)
Space Complexity	O(K)

---

Interview One-Liner

Maintain a Min Heap of size K. The top of the heap always represents the kth largest element seen so far.

---

Pattern Learned

Top K
+
Largest / Smallest

=> Heap