Java solution with explanation


  • 0
    Y

    The comments are within the source code below:

        public double[] medianSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0)
                return null;
            
            int n = nums.length;
            double[] res = new double[n - k + 1];
            int index = 0;
            
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder()); // for the half with smaller numbers
            PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); // for the half with bigger numbers
        
            for (int i = 0; i < n; i++) {
                // add new element into one of the heap
                if (maxHeap.isEmpty() || nums[i] < maxHeap.peek())
                    maxHeap.offer(nums[i]);
                else
                    minHeap.offer(nums[i]);
            
                // remove element outside of window
                if (i >= k) {
                    if (nums[i - k] <= maxHeap.peek())
                        maxHeap.remove(nums[i - k]);
                    else
                        minHeap.remove(nums[i - k]);
                }
    
                // balance two heaps, make sure maxHeap contains one more element if k is odd.
                while (minHeap.size() >= maxHeap.size() + 1)
                    maxHeap.offer(minHeap.poll());
    
                while (maxHeap.size() > minHeap.size() + 1)
                    minHeap.offer(maxHeap.poll());
    
                // add result
                if (i >= k - 1) {
                    if (k % 2 == 1)
                        res[index] = maxHeap.peek();
                    else
                        res[index] = ((double)maxHeap.peek() + minHeap.peek()) / 2;
                    index++;
                }
            }
            return res;
        }
    

Log in to reply
 

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