# Why is my O(1) space solution wrong?

• I was thinking what if the input dataStream is really huge, for example 1TB, that means you will not have enough space to store all the elements in your queues.

Thus, I'm trying to limit the size of each queue to 3, basically you only need to use the Max from left Q or Min from right Q, as long as you have the size of each Q stored in single integers.

``````class MedianFinder {

PriorityQueue<Long> leftQ;
PriorityQueue<Long> rightQ;
int leftCount = 0, rightCount = 0;

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

// Adds a number into the data structure.
rightCount++;

rightCount--;
leftCount++;

if(rightCount < leftCount){
rightCount++;
leftCount--;
}
}

// Returns the median of current data stream
public double findMedian() {
return rightCount > leftCount ? rightQ.peek() : (leftQ.peek() + rightQ.peek()) / 2.0;
}

private void addToQueue(PriorityQueue<Long> Q, long num, boolean isReverse){
if(Q.size() < 3) {
Q.offer(num);
return;
}

if(isReverse){ // Add to left Q
if(num > Q.peek()){
Q.poll();
Q.offer(num);
}
} else{ // Add to right Q
if (num < Q.peek()){
Q.poll();
Q.offer(num);
}
}
}
};``````

• The test case not passed:

Input:
Output:
[1.00000,1.50000,2.00000,2.50000,3.00000,3.50000,4.00000,4.50000,5.00000,6.00000]
Expected:
[1.00000,1.50000,2.00000,2.50000,3.00000,3.50000,4.00000,4.50000,5.00000,5.50000]

• I made similar mistake, you have poll the 6 from the right Q, then you can not get right ans as (5+6)/2;

• @Chandlearn Yep, looks like we have to keep all the values using O(n) space. Otherwise, there got to be a case that we miss.

Thanks,
Ran3

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