Find Median from Data Stream
The median is the middle value in an ordered integer list.
If the size of the list is even, there are two middle values. The median is the average of those two values.
Implement the MedianFinder class:
- MedianFinder() initializes the object.
- addNum(int num) adds an integer from the data stream.
- findMedian() returns the median of all elements added so far.
Answers within 10^-5 of the actual answer are accepted.
Example 1
Input
n = 4 stream = [1, 2, 3, 4]
Output
2.50000
Explanation
After adding all four numbers, the sorted data is:
[1, 2, 3, 4]
The two middle values are 2 and 3.
median = (2 + 3) / 2 = 2.5
Example 2
Input
n = 5 stream = [5, 3, 8, 2, 7]
Output
5.00000
Explanation
The sorted data is:
[2, 3, 5, 7, 8]
The middle value is 5.
Constraints
Hints:
Hint 1
Maintain two heaps:
- A max-heap for the smaller half.
- A min-heap for the larger half.
Hint 2
Keep the sizes of the two heaps balanced so that they differ by at most 1.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 22, 2026
Last updated
Aug 22, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output