Leetcode 295. Find Median from Data Stream

Problem

Leetcode 295 - Find Median from Data Stream

Example:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]
Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Approach

We can simply sort the array, and return the median of the array when we’re finding median.

Here is the Python code for the solution:

class MedianFinder:

    def __init__(self):
        self.arr = []
        heapq.heapify(self.arr)

    def addNum(self, num: int) -> None:
        self.arr.append(num)

    def findMedian(self) -> float:
        self.arr.sort()
        if len(self.arr) % 2 == 0:
            return (self.arr[len(self.arr)//2] + self.arr[len(self.arr)//2-1])/2
        else:
            return (self.arr[len(self.arr)//2])
        

Time Complexity and Space Complexity

Time Complexity: $O(m * log n)$ for findMedian(), and O(1) for addNum()

Space Complexity: $O(n)$