EasyNo. 0703
Kth Largest Element in a Stream — LeetCode 703 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Tree, Design, Binary Search Tree, Binary Tree, Data Stream, Heap (Priority Queue)
- On a study list
- NeetCode 150
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.
Python solution
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.min_q = []
for x in nums:
self.add(x)
def add(self, val: int) -> int:
heappush(self.min_q, val)
if len(self.min_q) > self.k:
heappop(self.min_q)
return self.min_q[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)Complexity
- Time
- O(n × log k)
- Space · auxiliary
- O(k)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 703. Kth Largest Element in a Stream is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1825 | Finding MK Average | Hard |
| 2102 | Sequentially Ordinal Rank Tracker | Hard |
| 0855 | Exam Room | Medium |
| 1845 | Seat Reservation Manager | Medium |
| 2642 | Design Graph With Shortest Path Calculator | Hard |
| 0023 | Merge k Sorted Lists | Hard |
Frequently asked questions
- How hard is LeetCode 703. Kth Largest Element in a Stream?
LeetCode 703. Kth Largest Element in a Stream is rated Easy on LeetCode.
- What is the time complexity of LeetCode 703. Kth Largest Element in a Stream?
The Python solution on this page runs in O(n × log k).
- What is the space complexity of LeetCode 703. Kth Largest Element in a Stream?
The Python solution on this page uses O(k) auxiliary space.
- What topics does LeetCode 703. Kth Largest Element in a Stream cover?
LeetCode 703. Kth Largest Element in a Stream is tagged Tree, Design, Binary Search Tree, Binary Tree, Data Stream and Heap (Priority Queue) on LeetCode.