As we have seen earlier, questions that require you the k-th minimum/maximum/largest/smallest are a great way to exercise your heap datastructure skills.
A heap is a data structure that rearranges itself after each insertion or deletion in such a way that you can always get the maximum or minimum element from a dataset in constant time.
In this scenario we need a min heap, where the root is the minimum value node. So, if we maintain k largest elements in it, the root will be the k-th largest element.
By maintaining k elements, I mean that after insertion if the exceeds k, just - this will remove the current root.
Code:
Java
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> kTh = new PriorityQueue<>();
for (int a : nums) {
kTh.add(a);
if (kTh.size() > k) kTh.poll();
}
return kTh.peek();
}
}
Big O Analysis
- Runtime The runtime complexity here is as since the heap insertion and deletion takes time and we would do that for all the elements in the array.
- Memory The memory usage is since we are maintaining a priority queue (heap) of k elements.
— A