Approach 1: Priority Queue
This is a standard approach where we maintain k elements in a min-heap (min priority queue). This way, the element on the top of the queue will always be the k-th largest element.
class KthLargest {
public:
priority_queue<int, vector<int>, greater<int>> pq;
int k;
KthLargest(int k, vector<int>& nums) {
this->k = k;
for (int i : nums) {
pq.push(i);
if (pq.size()>k)
pq.pop();
}
}
int add(int val) {
pq.push(val);
if (pq.size()>k)
pq.pop();
return pq.top();
}
};
Time complexity: O(nlogk) where n is the number of elements in nums + number of calls to the add() function
Space complexity: O(k)
Approach 2: Using BST
This is a rather interesting approach and is not very straightforward. The worst time complexity is worse as well (average TC is better though) but I thought it would be nice to present an alternate interesting approach. You can read about the approach here: LeetCode Article on BST.
class KthLargest {
TreeNode root;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
for (int num: nums) root = add(root, num);
}
public int add(int val) {
root = add(root, val);
return findKthLargest();
}
private TreeNode add(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
root.count++;
if (val < root.val) root.left = add(root.left, val);
else root.right = add(root.right, val);
return root;
}
public int findKthLargest() {
int count = k;
TreeNode walker = root;
while (count > 0) {
int pos = 1 + (walker.right != null ? walker.right.count : 0);
if (count == pos) break;
if (count > pos) {
count -= pos;
walker = walker.left;
} else if (count < pos)
walker = walker.right;
}
return walker.val;
}
class TreeNode {
int val, count = 1;
TreeNode left, right;
TreeNode(int v) { val = v; }
}
}
Time complexity: O(logn) average, O(n) worst case
Space complexity: O(n)