295. Find Median from Data Stream

Find Median from Data Stream

Problem Description

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

• For example, for arr = [2,3,4], the median is 3.
• For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

• MedianFinder() initializes the MedianFinder object.
• void addNum(int num) adds the integer num from the data stream to the data structure.
• double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

 

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

 

Constraints:

• -105 <= num <= 105
• There will be at least one element in the data structure before calling findMedian.
• At most 5 * 104 calls will be made to addNum and findMedian.

 

Follow up:

• If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
• If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

Approach) Brute Force

var MedianFinder = function() {
    this.a = [];
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    this.a.push(num);
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    this.a.sort((x, y) => x - y);
    let n = this.a.length;
    let m = n >> 1;
    return n & 1 ? this.a[m] : (this.a[m - 1] + this.a[m]) / 2;
};

/** 
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */

Approach) Binary Search

var MedianFinder = function() {
    this.ary = [];
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    var low = 0 ; 
    var high = this.ary.length-1;
    
    while(low <= high)
        {
            var mid = Math.floor((high + low)/2);
            
            if(this.ary[mid]  < num)
                {
                    low = mid+1;
                }
            else
                {
                    high =mid-1;
                }
        }
    
    // insert at  location trick for javascript array.
    this.ary.splice(low, 0, num);
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    if(this.ary.length % 2 ==0)
        {
            var mid = this.ary.length/2;
            return (this.ary[mid] + this.ary[mid-1])/2;
        }
    else
        {
            var mid = Math.floor(this.ary.length/2);
            return (this.ary[mid]);
        }
};

/** 
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */




Approach) Min-Max Heap

/**
 * initialize your data structure here.
 */
var MedianFinder = function() {
    this.mxh=new heap((a,b)=>b-a,[]);
    this.mnh=new heap((a,b)=>a-b,[]);
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    if(this.mxh.size()<=0)
        return this.mxh.insert(num);
    
    if(this.mnh.size()<=0){
        if(num>=this.mxh.top())
            return this.mnh.insert(num);
        else{
            this.mxh.insert(num);
            this.mnh.insert(this.mxh.extract());            
            return;
        }
    }
    
    if(num>=this.mnh.top()){
        if(this.mnh.size()<=this.mxh.size())
            return this.mnh.insert(num);
        else{
            this.mnh.insert(num);
            this.mxh.insert(this.mnh.extract());
            return;
        }
    }
    else{
        if(this.mxh.size()<=this.mnh.size())
            return this.mxh.insert(num);
        else{
            this.mxh.insert(num);
            this.mnh.insert(this.mxh.extract());
            return;
        }
    }
    
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    if(this.mnh.size()<=0)
        return this.mxh.top();
    if(this.mnh.size()==this.mxh.size())
        return (this.mnh.top()+this.mxh.top())/2;
    return this.mnh.size()>this.mxh.size()?this.mnh.top():this.mxh.top();
};

/** 
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */


/*Heap Implementation JavaScript*/
let heap = function(comparator,array){
    this.ar=[...array];/*No mutation*/    
    this.comparator=comparator;//0/+ve/-ve
    
    /*build heap*/
    for(let i=parseInt((this.ar.length-1)/2);i>=0;i--){
        this.heapify(i);
    }
};
heap.prototype.heapify = function(i){
    if(i>=this.ar.length)
        return;
    let temp=i;
    if((2*i)+1<this.ar.length&&this.comparator(this.ar[(2*i)+1],this.ar[temp])<0)
        temp=(2*i)+1;
    if((2*i)+2<this.ar.length&&this.comparator(this.ar[(2*i)+2],this.ar[temp])<0)
        temp=(2*i)+2;
    
    if(temp!==i){
        /*Swap*/
        let copy=this.ar[temp];
        this.ar[temp]=this.ar[i];
        this.ar[i]=copy;
        
        this.heapify(temp);
    }
};

heap.prototype.insert = function(data){
    if(data==null)
        return false;
    this.ar.push(data);
        
    let i=this.ar.length-1;
    let parent=parseInt((i-1)/2);
    // comparator arguments should be inverted ???. Min Heap parent > child node swap heapify
    // while(parent>=0&&this.comparator(this.ar[parent],this.ar[i])<0){//Agar ye hai fir to loop mein nhi jayega
      
      while(parent>=0&&parent!=i&&this.comparator(this.ar[i],this.ar[parent])<0){
      
        this.heapify(parent);
        i=parent;
        parent=parseInt((parent-1)/2);        
    }
    return true;
};

heap.prototype.extract = function(){
    let copy=this.ar[0];
    this.ar[0]=this.ar[this.ar.length-1];
    this.ar.pop();
    this.heapify(0);
    return copy;
};
heap.prototype.size = function(){
    return this.ar.length;
};
heap.prototype.top = function(){
    return this.ar[0];
};

Approach) Bisection Search

As this list grows, it may become expensive to step through it and find the location of insertion. So, given that we'll be maintaining an ordered list, we can take advantage of bisection search to achieve faster search speed

• addNum is our workhorse:
  • Create a recursive function searchForInsertionIndex()
  • First account for special cases like empty or small lists
  • Find the middle index of the current list (list.length / 2, rounded down)
  • Check to see if num is equal to the middle or fits on either side (main base cases)
  • If not, recurse on the correct half of the list and move our storageIndex pointer +/- slice length / 2 (with appropriate rounding)
  • After each number is added, we calculate the median value depending on whether the list is even/odd in length
  • The Median is then stored on the object
• findMedian() is just a getter for this.median

var MedianFinder = function() {
  this.storage = [];
  this.median;
};

MedianFinder.prototype.addNum = function(num) {
  const searchForInsertionIndex = (orderedList, storageIndex=-1) => {
    const middleIndex = Math.floor(orderedList.length / 2);
    if (storageIndex < 0) {
      storageIndex = middleIndex;
    }
    const [leftNum, middleNum, rightNum] = [orderedList[middleIndex - 1], orderedList[middleIndex], orderedList[middleIndex + 1]];

    if (orderedList.length === 0 || middleNum === num) {
      return storageIndex;
    }
    if (orderedList.length === 1) {
      return num > middleNum ? storageIndex + 1 : storageIndex;
    }
    if (orderedList.length === 2) {
      if (num > middleNum) {
        return storageIndex + 1;
      }
      if (num > leftNum) {
        return storageIndex;
      }
      return storageIndex - 1;
    }
    if (rightNum >= num && middleNum < num) {
      return storageIndex + 1;
    }
    if (middleNum > num && leftNum <= num) {
      return storageIndex;
    }
    if (num > rightNum) {
      const rightList = orderedList.slice(middleIndex + 1);
      return searchForInsertionIndex(rightList, storageIndex + Math.floor(rightList.length / 2) + 1);
    }
    const leftList = orderedList.slice(0, middleIndex);
    return searchForInsertionIndex(leftList, storageIndex - Math.ceil(leftList.length / 2));
  };
  const insertionIndex = searchForInsertionIndex(this.storage);
  this.storage.splice(insertionIndex, 0, num);

  const middleIndex = Math.floor(this.storage.length / 2);
  this.median = this.storage.length % 2 === 0
    ? (this.storage[middleIndex] + this.storage[middleIndex - 1]) / 2
    : Math.floor(this.storage[middleIndex]);
};

MedianFinder.prototype.findMedian = function() {
  return this.median;
};

Approach) Linked List

/**
 * initialize your data structure here.
 */
    class Node {
        constructor(data){
            this.data = data;
            this.next = null;
        }
    }

var MedianFinder = function() {
    this.head = null;
    this.length = 0;
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    var newNode = new Node(num);
    if(this.head == null){
        this.head = newNode;
        this.length++;
        return;
    }
    
    // check if head.val is greater than num: Enter head
    // elseif traverse and find when head.next.val is greater than val
    // then insert:newNode.next = head.next, head.next = newNode;
    // traverse ends, then last head.next = newnode.
    if(this.head.data > num){
       // insert at head
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
        return;
     }else{
        var head = this.head;
        while(head.next != null){
            if(head.next.data > num){
               break;
               }
            head = head.next;
        }
        newNode.next = head.next;
        head.next = newNode;    
        this.length++;
        return
     }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    console.log(this.head)
    var count = 0;
    // when even  this.length%2 == 0
    // this.length/2 then return value of this index and next
    // when odd   this.length%2 != 0 math.round(length/2) -1<= roundup
    if(this.length%2 != 0){
       var returnIndex = Math.round(this.length/2) - 1;
        head = this.head;
        while(head){
          if(count == returnIndex){
              console.log(head.data)
             return head.data;
          }
          head = head.next;
          count++
        }
    }else{
        var firstReturnIndex = ((this.length/2)-1);
        head = this.head;
        while(head){
          if(count == firstReturnIndex){
             console.log((head.data + head.next.datal)/2)
             return (head.data + head.next.data)/2
          }
          head = head.next;
          count++              
       }
    }
    
};

/** 
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */

Conclusion

That’s all folks! In this post, we solved LeetCode problem 295. Find Median from Data Stream

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!