LeetCode : 480. Sliding Window Median

[congr]

https://leetcode.com/problems/sliding-window-median/

[congr]

class Solution {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    public double[] medianSlidingWindow(int[] nums, int k) {
        double[] res = new double[nums.length - k + 1];

        for (int i = 0; i < k; i++) add(nums[i]);
        res[0] = findMedian();

        for (int i = k, j = 1; i < nums.length; i++) {
            remove(nums[i-k]);
            add(nums[i]);
            res[j++] = findMedian();
        }

        return res;
    }

    void add(int n) {
        if (minHeap.isEmpty()) { // at first
            minHeap.add(n);
            return;
        }

        if (minHeap.peek() <= n) minHeap.add(n); 
        else maxHeap.add(n);

        rebalance();
    }

    void remove(int n) {
        if (minHeap.contains(n)) minHeap.remove(n);
        else maxHeap.remove(n);

        rebalance();
    }

    void rebalance() {
        int minHeapSize = minHeap.size(), maxHeapSize = maxHeap.size();
        if (Math.abs(minHeapSize - maxHeapSize) <= 1)  return;

        if (minHeapSize < maxHeapSize) minHeap.add(maxHeap.remove());
        else maxHeap.add(minHeap.remove());
    }

    double findMedian() {
        double median = 0d;
        // with the updated heap size, find median
        if (minHeap.size() == maxHeap.size()) median = ((double)minHeap.peek() + (double)maxHeap.peek()) / 2;
        else if (minHeap.size() > maxHeap.size()) median = minHeap.peek(); 
        else median = maxHeap.peek();
        return median;
    }
}