HardNo. 0295

Find Median from Data Stream — LeetCode 295 Python Solution

Topics
Design, Two Pointers, Data Stream, Sorting, Heap (Priority Queue)
Reading time
4 min

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

PythonSolution
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

Related problems
No.ProblemDifficulty
0284Peeking IteratorMedium
0307Range Sum Query - MutableMedium
0715Range ModuleHard
2276Count Integers in IntervalsHard
0658Find K Closest ElementsMedium
0703Kth Largest Element in a StreamEasy

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.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.