Sponsored
Sponsored
Using a min-heap of size k can efficiently keep track of the kth largest element. This approach relies on the property of a heap where the smallest element (the root) in a min-heap can be accessed in constant time.
Steps:
Time Complexity: O(n log k) for initialization and O(log k) per add operation.
Space Complexity: O(k) for the heap.
1import java.util.PriorityQueue;
2
3class KthLargest {
4 private int k;
5 private PriorityQueue<Integer> minHeap;
6
7 public KthLargest(int k, int[] nums) {
8 this.k = k;
9 minHeap = new PriorityQueue<>(k);
10 for (int num : nums) {
11 add(num);
12 }
13 }
14
15 public int add(int val) {
16 if (minHeap.size() < k) {
17 minHeap.add(val);
18 } else if (val > minHeap.peek()) {
19 minHeap.poll();
20 minHeap.add(val);
21 }
22 return minHeap.peek();
23 }
24}
25This Java solution uses a PriorityQueue as a min-heap. The object's constructor initializes the heap with the first k elements, adding any subsequent values through the add method, which maintains the size limit and order of the elements.