Find Median from Data Stream

Explore how to implement a MedianOfStream class that inserts numbers dynamically and finds the median in constant time using heaps. Understand the problem constraints, median calculation methods for odd and even sized data, and develop a solution to handle a continuous flow of integers effectively.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

Design a data structure that stores a dynamically changing list of integers and can find the median in constant time, $O(1)$ , as the list grows. To do that, implement a class named MedianOfStream with the following functionality:

Constructor(): Initializes an instance of the class.
insertNum(int num): Adds a new integer num to the data structure.
findMedian(): Returns the median of all integers added so far.

Note: The median is the middle value in a sorted list of integers.
For an odd-sized list (e.g., $[4, 5, 6]$ ), the median is the middle element: $5$ .
For an even-sized list (e.g., $[2, 4, 6, 8]$ ), the median is the average of the two middle elements: $(4 + 6) / 2 = 5$ .

Constraints:

$-10^5 \leq$ num $\leq 10^5$ , where num is an integer received from the data stream.
There will be at least one element in the data structure before the median is computed.
At most, $500$ calls will be made to the function that calculates the median.

JavaScript

usercode > median_of_stream.js

import { MinHeap, MaxHeap } from './Heap.js'
/* The following definition is for MinHeap.
  You can use the same methods for MaxHeap.
  class MinHeap {
    size();          // return number of elements
    peek();          // return top element without removing
    push(val);       // insert element
    pop();           // remove and return top element
  }
*/
class medianOfStream {
  constructor() {
      // Write your code here
  }
  // This function should take a number and store it  
  insertNum(num) {
      // Write your code here
      
  }
  // This function should return the median of the stored numbers  
  findMedian() {
      // Replace this placeholder return statement with your code
      return 0.0
  }
}
export default medianOfStream;

Find Median from Data Stream

Find Median from Data Stream

Statement

Examples

Understand the problem

Figure it out!

Try it yourself