Back

Find Median from Data Stream

hard

The median is the middle value in an ordered integer list. If the size of the list is even, the median is the mean of the two middle values.

Implement the MedianFinder class:

  • MedianFinder() initializes the object.
  • void addNum(int num) adds the integer num to the data structure.
  • double findMedian() returns the median of all elements so far.

Test Cases

Copy an input into the main harness and Run to verify
Input
addNum(1), addNum(2), findMedian(), addNum(3), findMedian()
Expected Output
1.5, 2.0

Explanation: After 1 and 2 the median is 1.5; after adding 3 the median is 2.

Constraints

  • -10^5 <= num <= 10^5
  • There will be at least one element before findMedian is called.
  • At most 5 * 10^4 calls will be made to addNum and findMedian.

Hints

Hint 1 — click to reveal

Sorting on every query is far too slow — you only ever need the middle, not the whole order.

Hint 2 — click to reveal

Keep the smaller half in a max-heap and the larger half in a min-heap, and keep their sizes balanced.

Java Compiler

Powered by OneCompiler. Starter code loads automatically — edit and hit Run.