Find Median from Data Stream [LC#295]
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.
- For example, for arr = [2,3,4], the median is 3.
- For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Intuition
- We can easily find median if we have access to the 2 middle elements.
- The middle elements are largest of the first half and smallest of the second half if the array was sorted
- We can maintain first half of elements in a max heap and second half in min heap
- Always maintain insertion so that max heap has at most 1 value more than the min heap
Code
class MedianFinder:
def __init__(self):
self.low = [] # stores n or n+1 elements
self.high = [] # stores n elements
def add(self, num: int) -> None:
val = heapq.heappushpop(self.low, -num)
heapq.heappush(self.high, -val)
if len(self.low) < len(self.high):
val = heapq.heappop(self.high)
heapq.heappush(self.low, -val)
def find_median(self) -> float:
if len(self.low) > len(self.high):
return -self.low[0]
return (-self.low[0] + self.high[0])/2
Time complexity
for each insertion and median can be computed in always for the heaps