Easy to Understand Java solution, 28ms, beats 92%

• Still the 2 priority queues based solutions.
However, I think we can save a lot of the operations between the 2 queues as used in https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1

I only do queue.offer(queue2.poll()) when the diff between the queue sizes is 2. This will save some time I guess.

``````class MedianFinder {

PriorityQueue<Integer> leftQ;
PriorityQueue<Integer> rightQ;
Double median = null;

public MedianFinder(){
leftQ = new PriorityQueue<>(Comparator.reverseOrder());
rightQ = new PriorityQueue<>();
}

// Adds a number into the data structure.
if(median == null){
leftQ.offer(num);
median = num*1.0;
} else if(num > median){
rightQ.offer(num);
median = findMedian(rightQ, leftQ);

} else {
leftQ.offer(num);
median = findMedian(leftQ, rightQ);
}

}

private double findMedian(PriorityQueue<Integer> leftQ, PriorityQueue<Integer> rightQ){
double result = 0;
if(leftQ.size() - rightQ.size() == 2)
rightQ.offer(leftQ.poll());

if(leftQ.size() - rightQ.size() == 1)
result = leftQ.peek()*1.0;
else
result = (leftQ.peek() + rightQ.peek())*1.0 / 2;
return result;
}

// Returns the median of current data stream
public double findMedian() {
return median;
}
};

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.