Algorithm

Problem Name: 295. Find Median from Data Stream

Problem Link: https://leetcode.com/problems/find-median-from-data-stream/
 

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..

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#define PRINT(MF, D) do { } while (0)
#define DUMP(MF) do { } while (0)
​
typedef struct {
    int *p;
    int sz;
    int n;
} MedianFinder;
​
/** initialize your data structure here. */
MedianFinder* medianFinderCreate() {
    MedianFinder *mf;
    int *buff;
    int sz;
    
    sz = 100;
    buff = malloc(sz * sizeof(int));
    mf = calloc(1, sizeof(*mf));
    //assert(buff && mf);
    mf->p = buff;
    mf->sz = sz;
​
    return mf;
}
​
int find_x(int *p, int start, int end, int num) {
    int x = 0;
    while (start  < = end) {
        x = (end + start) / 2;
        if (p[x] > num) {
            end = x - 1;
        } else if (p[x]  <  num) {
            start = x + 1;
        } else {
            break;
        }
    }
    return x;
}
void medianFinderAddNum(MedianFinder* mf, int num) {
    int i, x;
    
    if (!mf) return;
    
    if (mf->n == mf->sz) {
        // enlarge the buffer
        mf->sz *= 2;
        mf->p = realloc(mf->p, mf->sz * sizeof(int));
        //assert(mf->p);
    }
    if (mf->n == 0) {
        mf->p[mf->n ++] = num;
DUMP(mf);
        return;
    }
    
    x = find_x(mf->p, 0, mf->n - 1, num);
    if (mf->p[x]  < = num) x ++;
    for (i = mf->n - 1; i >= x; i --) {
        mf->p[i + 1] = mf->p[i];
    }
    mf->p[x] = num;
    mf->n ++;
DUMP(mf);
}
​
double medianFinderFindMedian(MedianFinder* mf) {
    double d;
    
    if (mf->n % 2) {
        d = mf->p[mf->n / 2];
    } else {
        d  = mf->p[mf->n / 2];
        d += mf->p[mf->n / 2 - 1];
        d /= 2;
    }
PRINT(mf, d);
    return d;
}
​
void medianFinderFree(MedianFinder* mf) {
    free(mf->p);
    free(mf);
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]

Output

x
–
+
cmd
[null, null, null, 1.5, null, 2.0]

#2 Code Example with C++ Programming

Code - C++ Programming


class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {}
    
    void addNum(int num) {
        (left.empty() || num <= left.top()) ? left.push(num) : right.push(num);
        if(left.size() > right.size() + 1){
            right.push(left.top());
            left.pop();
        }
        if(right.size() > left.size()){
            left.push(right.top());
            right.pop();
        }
    }
    
    double findMedian() {
        return left.size() > right.size()? left.top() : (left.top() + right.top()) / 2.0;
    }

private:
    priority_queue < int>left;
    priority_queue<int, vector<int>, greater < int>>right;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]

Output

x
–
+
cmd
[null, null, null, 1.5, null, 2.0]

#3 Code Example with Java Programming

Code - Java Programming


class MedianFinder {
    
    private final PriorityQueue minQueue;
    private final PriorityQueue < Integer> maxQueue;
    
    public MedianFinder() {
        this.minQueue = new PriorityQueue<>();
        this.maxQueue = new PriorityQueue < >((a, b) -> b - a);
    }
    
    public void addNum(int num) {
        maxQueue.add(num);
        minQueue.add(maxQueue.poll());
        if (maxQueue.size()  <  minQueue.size()) {
            maxQueue.add(minQueue.poll());
        }
    }
    
    public double findMedian() {
        return maxQueue.size() > minQueue.size() ? 
            ((double) maxQueue.peek()) : 
            ((maxQueue.peek() + minQueue.peek()) / (2.0));
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]

Output

x
–
+
cmd
[null, null, null, 1.5, null, 2.0]

#4 Code Example with Javascript Programming

Code - Javascript Programming


const MedianFinder = function() {
  this.arr = [];
};

MedianFinder.prototype.addNum = function(num) {
  const bs = n => {
    let start = 0;
    let end = this.arr.length;
    while (start  <  end) {
      let mid = ~~((start + end) / 2);
      if (n > this.arr[mid]) start = mid + 1;
      else end = mid;
    }
    this.arr.splice(start, 0, n);
  };
  if (this.arr.length === 0) this.arr.push(num);
  else bs(num);
};

MedianFinder.prototype.findMedian = function() {
  const mid = ~~(this.arr.length / 2);
  return this.arr.length % 2 === 0
    ? (this.arr[mid - 1] + this.arr[mid]) / 2
    : this.arr[mid];
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]

Output

x
–
+
cmd
[null, null, null, 1.5, null, 2.0]

#5 Code Example with Python Programming

Code - Python Programming


class MedianFinder:

    def __init__(self):
        self.l = []
        self.r = []
        self.m = []

    def addNum(self, num):
        if not self.m:
            self.m = [num]
        elif len(self.m) == 1:
            m = self.m[0]
            if num >= m:
                self.m = [m, heapq.heappushpop(self.r, num)]
            else:
                self.m = [-heapq.heappushpop(self.l, -num), m]
        else:
            m1, m2 = self.m
            if num >= m2:
                heapq.heappush(self.r, num)
                heapq.heappush(self.l, -m1)
                self.m = [m2]
            elif num <= m1:
                heapq.heappush(self.l, -num)
                heapq.heappush(self.r, m2)
                self.m = [m1]
            else:
                heapq.heappush(self.l, -m1)
                heapq.heappush(self.r, m2)
                self.m = [num]

    def findMedian(self):
        return sum(self.m) / len(self.m)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]

Output

x
–
+
cmd
[null, null, null, 1.5, null, 2.0]

#6 Code Example with C# Programming

Code - C# Programming


using System;

namespace LeetCode
{
    public class _0295_FindMedianFromDataStream
    {
        private readonly MinPriorityQueue minPQ;
        private readonly MaxPriorityQueue maxPQ;

        /** initialize your data structure here. */
        public _0295_FindMedianFromDataStream()
        {
            minPQ = new MinPriorityQueue();
            maxPQ = new MaxPriorityQueue();
        }

        public void AddNum(int num)
        {
            minPQ.Insert(num);
            maxPQ.Insert(minPQ.DeleteMin());

            if (minPQ.Size()  <  maxPQ.Size())
                minPQ.Insert(maxPQ.DeleteMax());
        }

        public double FindMedian()
        {
            if (minPQ.Size() > maxPQ.Size())
                return minPQ.Min();
            else
                return (minPQ.Min() + maxPQ.Max()) / 2.0;
        }

        public class MinPriorityQueue : PriorityQueue
        {
            public MinPriorityQueue() : base() { }

            public MinPriorityQueue(int initCapacity) : base(initCapacity) { }

            protected override void Sink(int k)
            {
                while (2 * k  < = N)
                {
                    int j = 2 * k;
                    if (j < N && pq[j] > pq[j + 1]) j++;
                    if (pq[k]  < = pq[j]) break;
                    Swap(k, j);
                    k = j;
                }
            }

            protected override void Swim(int k)
            {
                while (k > 1 && pq[k / 2] > pq[k])
                {
                    Swap(k / 2, k);
                    k = k / 2;
                }
            }

            public int Min() => First();

            public int DeleteMin() => Delete();
        }

        public class MaxPriorityQueue : PriorityQueue
        {
            public MaxPriorityQueue() : base() { }

            public MaxPriorityQueue(int initCapacity) : base(initCapacity) { }

            protected override void Sink(int k)
            {
                while (2 * k  < = N)
                {
                    int j = 2 * k;
                    if (j < N && pq[j] < pq[j + 1]) j++;
                    if (pq[k] >= pq[j]) break;
                    Swap(k, j);
                    k = j;
                }
            }

            protected override void Swim(int k)
            {
                while (k > 1 && pq[k / 2]  <  pq[k])
                {
                    Swap(k / 2, k);
                    k = k / 2;
                }
            }

            public int Max() => First();

            public int DeleteMax() => Delete();
        }

        public abstract class PriorityQueue
        {
            protected int N;
            protected int[] pq;

            public PriorityQueue() : this(1) { }

            public PriorityQueue(int initCapacity)
            {
                this.N = 0;
                pq = new int[initCapacity + 1];
            }

            public bool IsEmpty() => N == 0;

            public int Size() => N;

            public int First()
            {
                if (IsEmpty()) { throw new ArgumentOutOfRangeException(); }
                return pq[1];
            }

            public void Insert(int x)
            {
                if (N >= pq.Length - 1)
                    Resize(pq.Length * 2);

                pq[++N] = x;
                Swim(N);
            }

            protected abstract void Swim(int k);

            public int Delete()
            {
                var result = pq[1];
                Swap(1, N--);
                Sink(1);
                pq[N + 1] = 0;
                if (N > 0 && N == (pq.Length - 1) / 4)
                    Resize(pq.Length / 2);

                return result;
            }

            protected abstract void Sink(int k);

            private void Resize(int newCapacity)
            {
                var temp = new int[newCapacity + 1];
                for (int i = 1; i  < = N; i++)
                    temp[i] = pq[i];

                pq = temp;
            }

            protected void Swap(int index1, int index2)
            {
                var temp = pq[index1];
                pq[index1] = pq[index2];
                pq[index2] = temp;
            }
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]

Output

x
–
+
cmd
[null, null, null, 1.5, null, 2.0]
Advertisements

Demonstration

Previous
#292 Leetcode Nim Game Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#297 Leetcode Serialize and Deserialize Binary Tree Solution in C, C++, Java, JavaScript, Python, C# Leetcode