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.
1using System;
2using System.Collections.Generic;
3
4public class KthLargest {
5 private int k;
6 private SortedSet<(int, int)> minHeap;
7 private int counter = 0;
8
9 public KthLargest(int k, int[] nums) {
10 this.k = k;
11 minHeap = new SortedSet<(int, int)>();
12 foreach (var num in nums) {
13 Add(num);
14 }
15 }
16
17 public int Add(int val) {
18 minHeap.Add((val, counter++));
19 if (minHeap.Count > k) {
20 minHeap.Remove(minHeap.Min);
21 }
22 return minHeap.Min.Item1;
23 }
24}
25In this C# solution, a SortedSet is used which acts like a priority queue by keeping the elements sorted. It requires a tuple to manage duplicate values, using a counter to keep distinction.