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.
1class KthLargest {
2 constructor(k, nums) {
3 this.k = k;
4 this.minHeap = [];
5 for (const num of nums) {
6 this.add(num);
7 }
8 }
9
10 add(val) {
11 if (this.minHeap.length < this.k) {
12 this.minHeap.push(val);
13 this.minHeap.sort((a, b) => a - b);
14 } else if (val > this.minHeap[0]) {
15 this.minHeap[0] = val;
16 this.minHeap.sort((a, b) => a - b);
17 }
18 return this.minHeap[0];
19 }
20}
21JavaScript lacks a native priority queue, so this solution implements a simple array-based min-heap, maintaining order via sorting. While less efficient than a true min-heap, this method remains functional for this problem scope.