67 / 75
Easy
Kth Largest Element in a Stream
#67heapdesignbinary-search-treedata-stream
Maintain min-heap of size k; top element is always kth largest.
Example:
Input:
KthLargest(3, [4,5,8,2]), add(3), add(5), add(10), add(9), add(4)Output:
[null, 4, 5, 5, 8, 8]Common Mistakes:
- Using max-heap instead of min-heap (makes finding kth largest harder)
- Not maintaining heap size at exactly k
- Returning wrong element (should return peek, not val)
- Not handling case when heap size < k initially
Notes:
Min-heap of size k keeps k largest elements, top is kth largest. Constructor: O(n log k), add: O(log k). Space O(k).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Maintain min-heap of size k; top element is always kth largest.
Example:
Input:
KthLargest(3, [4,5,8,2]), add(3), add(5), add(10), add(9), add(4)Output:
[null, 4, 5, 5, 8, 8]Common Mistakes:
- Using max-heap instead of min-heap (makes finding kth largest harder)
- Not maintaining heap size at exactly k
- Returning wrong element (should return peek, not val)
- Not handling case when heap size < k initially
Notes:
Min-heap of size k keeps k largest elements, top is kth largest. Constructor: O(n log k), add: O(log k). Space O(k).
67/75
Kth Largest Element in a Stream