HardNo. 0295
Find Median from Data Stream — LeetCode 295 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Design, Two Pointers, Data Stream, Sorting, Heap (Priority Queue)
- On study lists
- Blind 75, NeetCode 150, Grind 75 and Top Interview 150
- Reading time
- 4 min
- Source
- leetcode.com
The problem
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
Example
- Input
- ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
- Output
- [null, null, null, 1.5, null, 2.0]
- Explanation
- MedianFinder medianFinder = new MedianFinder();
Python solution
class MedianFinder:
def __init__(self):
self.minq = []
self.maxq = []
def addNum(self, num: int) -> None:
heappush(self.minq, -heappushpop(self.maxq, -num))
if len(self.minq) - len(self.maxq) > 1:
heappush(self.maxq, -heappop(self.minq))
def findMedian(self) -> float:
if len(self.minq) == len(self.maxq):
return (self.minq[0] - self.maxq[0]) / 2
return self.minq[0]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()Complexity
- Time
- O(log n)
- Space · auxiliary
- O(n)where n is the number of elements
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 295. Find Median from Data Stream is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
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 |
|---|---|---|
| 0284 | Peeking Iterator | Medium |
| 0307 | Range Sum Query - Mutable | Medium |
| 0715 | Range Module | Hard |
| 2276 | Count Integers in Intervals | Hard |
| 0658 | Find K Closest Elements | Medium |
| 0703 | Kth Largest Element in a Stream | Easy |
Frequently asked questions
- How hard is LeetCode 295. Find Median from Data Stream?
LeetCode 295. Find Median from Data Stream is rated Hard on LeetCode.
- What is the time complexity of LeetCode 295. Find Median from Data Stream?
The Python solution on this page runs in O(log n).
- What is the space complexity of LeetCode 295. Find Median from Data Stream?
The Python solution on this page uses O(n), where n is the number of elements auxiliary space.
- What topics does LeetCode 295. Find Median from Data Stream cover?
LeetCode 295. Find Median from Data Stream is tagged Design, Two Pointers, Data Stream, Sorting and Heap (Priority Queue) on LeetCode.