Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

134. Find Median from Data Stream

HardDay 39 of 60Heap / Priority Queue

Design a class MedianFinder that receives numbers one at a time and can report the median of everything added so far. addNum(num) adds a number and findMedian() returns the median: the middle value if the count is odd, or the average of the two middle values if it is even.

Example 1
Input: ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]
Output: [null,null,null,1.5,null,2.0]
After 1 and 2 the median is (1 + 2) / 2 = 1.5. After adding 3 the middle of 1, 2, 3 is 2.
Constraints
  • -10^5 <= num <= 10^5
  • findMedian is called only after at least one addNum
  • At most 5 * 10^4 calls in total
Hints
Frequently asked at: Amazon, Microsoft, Google, Apple, Uber
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min