Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 295 Find Median from Data Stream - Problem Statement

The problem

Design a data structure that supports adding integers and finding the median.

MedianFinder(): Initialize the object.

addNum(num): Add num to the data structure.

findMedian(): Return the median of all elements added so far.

With operations addNum(1), addNum(2), findMedian(), addNum(3), findMedian():

  • After adding 1 and 2: sorted is [1, 2]. Median = (1 + 2) / 2 = 1.5.
  • After adding 3: sorted is [1, 2, 3]. Median = 2.

Constraints: −105≤num≤105-10^5 \le num \le 10^5. Up to 5×1045 \times 10^4 operations.