How do you solve Find Median from Data Stream on LeetCode?

Find Median from Data Stream (LeetCode #295) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log n) time complexity and O(n) space complexity. Key insight: Using two heaps allows us to efficiently manage the lower and upper halves of the data stream.

What is the brute force solution for Find Median from Data Stream?

The brute force approach for Find Median from Data Stream is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves storing all numbers in a list and sorting it every time we need to find the median. This is straightforward but inefficient for large data streams. The optimal Optimal Solution approach improves this to O(log n).

What are the interview tips for Find Median from Data Stream?

Explain your thought process clearly when discussing different approaches. Be prepared to discuss trade-offs between time and space complexity. Practice implementing heap operations, as they are commonly used in interview questions.

What are common mistakes when solving Find Median from Data Stream?

Not balancing the heaps properly after adding a number. Confusing the max-heap and min-heap operations.

#295

Find Median from Data Stream

Hard

Two PointersDesignSortingHeap (Priority Queue)Data StreamHeapSortingTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log n)
Space	O(n)	O(n)

💡

Intuition

Time O(log n)Space O(n)

The optimal solution uses two heaps (a max-heap for the lower half and a min-heap for the upper half) to efficiently maintain the median as numbers are added. This allows us to find the median in constant time after adding a number.

⚙️

Algorithm

4 steps

1Step 1: Initialize a max-heap for the lower half and a min-heap for the upper half.
2Step 2: When adding a number, decide which heap to add it to based on its value relative to the max of the lower half.
3Step 3: Balance the heaps if their sizes differ by more than one element.
4Step 4: To find the median, if the heaps are of equal size, return the average of the tops; otherwise, return the top of the larger heap.

solution.py21 lines

1import heapq
2
3class MedianFinder:
4    def __init__(self):
5        self.low = []  # max-heap
6        self.high = []  # min-heap
7
8    def addNum(self, num: int) -> None:
9        heapq.heappush(self.low, -num)
10        if self.low and self.high and (-self.low[0] > self.high[0]):
11            heapq.heappush(self.high, -heapq.heappop(self.low))
12
13        if len(self.low) > len(self.high) + 1:
14            heapq.heappush(self.high, -heapq.heappop(self.low))
15        elif len(self.high) > len(self.low):
16            heapq.heappush(self.low, -heapq.heappop(self.high))
17
18    def findMedian(self) -> float:
19        if len(self.low) > len(self.high):
20            return float(-self.low[0])
21        return (-self.low[0] + self.high[0]) / 2.0

ℹ

Complexity note: The time complexity is O(log n) for adding a number because we may need to balance the heaps, and O(1) for finding the median, as it only involves accessing the tops of the heaps.

1Using two heaps allows us to efficiently manage the lower and upper halves of the data stream.
2Balancing the heaps ensures that we can always retrieve the median in constant time.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.