Find Median From Data Stream

Back to problems

Leetcode

Medium

Heaps

Ordered Structures

Google

Amazon

Microsoft

Find Median From Data Stream

Design a data structure that supports adding numbers one by one and querying the current median at any time.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Median Finder

gfg

Problem Statement

Design a class-like data structure that processes integers from a stream.

You must support two operations:

addNum(num): insert an integer into the data structure
findMedian(): return the median of all inserted numbers so far

The median is:

the middle value when the number of elements is odd
the average of the two middle values when the number of elements is even

Your implementation should handle many insertions efficiently and answer median queries quickly.

Input Format

A sequence of operations on a stream of integers.
Each addNum operation provides one integer.
Each findMedian operation asks for the median of all numbers inserted so far.

Output Format

For each findMedian query, return the current median as a number.
If the count is even, return the average of the two middle values.

Constraints

Numbers may be negative, zero, or positive.
The stream size grows over time.
findMedian() is called only after at least one number has been inserted.
Aim for efficient per-operation updates and queries.

Examples

Sample cases returned by the problem API.

Example 1

Input

addNum(1)
addNum(2)
findMedian()
addNum(3)
findMedian()

Output

1.5
2

Explanation

After inserting 1 and 2, the median is (1 + 2) / 2 = 1.5. After adding 3, the sorted stream is [1, 2, 3], so the median is 2.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress