Sliding Window Median

Question

Question quoted from lintcode
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;

Idea

Any sorted array can be evenly broken into "left" and "right" chunk, i.e. equal size, and we can keep the median as the last element on the left. If the array cannot be broken evenly, we can make left chunk 1 element more than right chunk.

As we always want to visit the last element from the left chunk, we can use a maximum heap for it.
As we always want to visit the first element from the right chunk, we can use a minimum heap for it.

When the windows slides, remove an element and add another element.

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

class Element implements Comparable<Element> {
    public final int position;
    public final int value;

    Element(int position, int value) {
        this.position = position;
        this.value = value;
    }

    // These two methods were generated by Intellij
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;

        if (o == null || getClass() != o.getClass()) return false;

        Element element = (Element) o;

        if (position != element.position) return false;
        return value == element.value;
    }

    @Override
    public int hashCode() {
        int result = position;
        result = 31 * result + value;
        return result;
    }

    @Override
    public int compareTo(Element o) {
        return this.value - o.value;
    }
}

class Medianer {
    private PriorityQueue<Element> left = new PriorityQueue<>(Collections.reverseOrder());
    private PriorityQueue<Element> right = new PriorityQueue<>();
    public void slideIn(Element e) {
        if (left.size() == 0 && right.size() == 0){
            left.add(e);
            return;
        }

        Element out = left.size() > right.size()
                ? left.poll()
                : right.poll();

        Element bigger = e;
        Element smaller = out;
        if (out.value > e.value) {
            bigger = out;
            smaller = e;
        }

        left.add(smaller);
        right.add(bigger);
    }
    public void slideOut(Element e) {
        if (left.contains(e)) {
            left.remove(e);
            if (right.size() > 0) {
                left.add(right.poll());
            }
        } else {
            right.remove(e);
            right.add(left.poll());
        }
    }
    public int median() {
        return left.peek().value;
    }
}

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) {
        Medianer medianer = new Medianer();
        List<Integer> result = new LinkedList<Integer>();
        for(int i = 0; i < nums.length; i++) {
            if (i + k - 1 < nums.length) {
                if (i == 0) {
                    for (int j = 0; j < k; j++) {
                        int pos = i + j;
                        medianer.slideIn(new Element(pos, nums[pos]));
                    }
                } else {
                    int outPos = i - 1;
                    int inPos = i + k - 1;
                    medianer.slideOut(new Element(outPos, nums[outPos]));
                    medianer.slideIn(new Element(inPos, nums[inPos]));
                }
                result.add(medianer.median());
            } else {
                break;
            }
        }
        return result;
    }
}