Why is my O(1) space solution wrong?


  • 0
    R

    Based on solution https://leetcode.com/discuss/65107/share-my-java-solution-logn-to-insert-o-1-to-query.

    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.

    Please help take a look why the following solution is wrong?

    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.
        public void addNum(int num) {
            rightCount++;
            addToQueue(rightQ, (long)num, false);
            
            rightCount--;
            leftCount++;
            addToQueue(leftQ, rightQ.poll(), true);
            
            if(rightCount < leftCount){
                rightCount++;
                leftCount--;
                addToQueue(rightQ, leftQ.poll(), false);
            }
        }
    
        // 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);
                }
            }
        }
    };

  • 0
    R

    The test case not passed:

    Input:
    addNum(1),findMedian(),addNum(2),findMedian(),addNum(3),findMedian(),addNum(4),
    findMedian(),addNum(5),findMedian(),addNum(6),findMedian(),addNum(7),findMedian(),
    addNum(8),findMedian(),addNum(9),findMedian(),addNum(10),findMedian()
    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]


  • 0
    C

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


  • 0
    R

    @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


Log in to reply
 

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