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