# 33 ms JAVA solution, optimization is important

• maintain a left max heap and a right min heap, manage the size that left heap is always equal or one larger than right heap. It seems long, but it is really simple.

``````public class MedianFinder {
PriorityQueue<Integer> right = new PriorityQueue<>();
PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
// Adds a number into the data structure.
int ls = left.size();
int rs = right.size();
if (ls == 0) {
left.offer(num);
} else if (rs == 0) {
Integer lMax = left.peek();
if (lMax <= num) {
right.offer(num);
} else {
right.offer(left.poll());
left.offer(num);
}
} else {
Integer lMax = left.peek();
Integer rMin = right.peek();
if (ls == rs) {
if (num <= rMin) {
left.offer(num);
} else {
left.offer(right.poll());
right.offer(num);
}
} else {
if (num >= lMax) {
right.offer(num);
} else {
right.offer(left.poll());
left.offer(num);
}
}
}
}

// Returns the median of current data stream
public double findMedian() {
if (left.size() == 0) {
return 0.0;
}
if (left.size() == right.size()) {
return ((double)left.peek()+(double)right.peek())/2;
} else {
return left.peek();
}
}
};``````

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