Lintcode 360. Sliding Window Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Example

For array [1,2,7,8,5], moving window size k = 3. return [2,7,7]

At first the window is at the start of the array like this

[ | 1,2,7 | ,8,5] , return the median 2;

then the window move one step forward.

[1, | 2,7,8 | ,5], return the median 7;

then the window move one step forward again.

[1,2, | 7,8,5 | ], return the median 7;

Challenge

O(nlog(n)) time

Solution:
Use two PriorityQueue as a customerized queue. The max PQ saves the smaller element while the minPQ saves the bigger elements. We also need to rebalance the size of the two pq. The total number of elements of the two pqs are k.

Code (Java):

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer
     * @return: The median of the element inside the window at each moving
     */
    public List<Integer> medianSlidingWindow(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();

        if (nums == null || nums.length < k || k <= 0 || k > nums.length) {
            return ans;
        }

        MyQueue myQueue = new MyQueue();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (myQueue.size() < k) {
                myQueue.offer(num);
            } else {
                myQueue.delete(nums[i - k]);
                myQueue.offer(num);
            }

            if (i >= k - 1) {
                ans.add(myQueue.getMedian());
            }
        }

        return ans;
    }
}

class MyQueue {
    private PriorityQueue<Integer> maxPQ;
    private PriorityQueue<Integer> minPQ;

    public MyQueue() {
        maxPQ = new PriorityQueue<>(Collections.reverseOrder());
        minPQ = new PriorityQueue<>();
    }

    public int size() {
        return maxPQ.size() + minPQ.size();
    }

    // minPQ.size == maxPQ.size OR
    // maxPQ.size - minPQ.size == 1
    //
    public void offer(int num) {
        if (maxPQ.isEmpty() || num <= maxPQ.peek()) {
            maxPQ.offer(num);
        } else {
            minPQ.offer(num);
        }

        rebalance();
    }

    public void delete(Integer num) {
        if (!maxPQ.isEmpty() && num <= maxPQ.peek()) {
            maxPQ.remove(num);
        } else {
            minPQ.remove(num);
        }

        rebalance();
    }

    public int getMedian() {
        return maxPQ.peek();
    }

    private void rebalance() {
        if (maxPQ.size() - minPQ.size() > 1) {
            minPQ.offer(maxPQ.poll());
        }

        if (minPQ.size() > maxPQ.size()) {
            maxPQ.offer(minPQ.poll());
        }
    }
}