public double[] medianSlidingWindow(int[] nums, int k) {

int len = nums.length;

int mid = k / 2;

List<Integer> window = new ArrayList<>();

for (int j = 0; j < k; j++) {

window.add(nums[j]);

}

Collections.sort(window);

if ((k & 1) == 0) {

int lenNew = len - 2 * mid + 1;

double[] returned = new double[lenNew];

for (int i = 0; i < lenNew - 1; i++) {

returned[i] = findMedianFromEven(window, mid);

int idx = window.indexOf(nums[i]);

int newValue = nums[i + k];

updateWindow(window, newValue, idx, k);

}

returned[lenNew - 1] = findMedianFromEven(window, mid);

return returned;

} else {

int lenNew = len - 2 * mid;

double[] returned = new double[lenNew];

for (int i = 0; i < lenNew - 1; i++) {

returned[i] = findMedianFromOdd(window, mid);

int idx = window.indexOf(nums[i]);

int newValue = nums[i + k];

updateWindow(window, newValue, idx, k);

}

returned[lenNew - 1] = findMedianFromOdd(window, mid);

return returned;

}

}

private double findMedianFromEven(List<Integer> window, int mid) {

return ((long)window.get(mid - 1) + (long)window.get(mid)) / 2.0;

}

private double findMedianFromOdd(List<Integer> window, int mid) {

return window.get(mid);

}

private void updateWindow(List<Integer> window, int newValue, int idx, int k) {

while(0 <= idx && idx < k) {

if (idx > 0 && window.get(idx - 1) > newValue) {

window.set(idx, window.get(idx - 1));

idx -= 1;

} else if (idx < k - 1 && window.get(idx + 1) < newValue) {

window.set(idx, window.get(idx + 1));

idx += 1;

} else {

window.set(idx, newValue);

return;

}

}

window.set(idx, newValue);

}

public double[] medianSlidingWindow2(int[] nums, int k) {

Comparator<Pair> comp = new Comparator<Pair>(){

public int compare(Pair p1, Pair p2) {

int diff = Integer.compare(p1.value, p2.value);

if (diff != 0) return diff;

return Integer.compare(p1.index, p2.index);

}

};

TreeSet<Pair> left = new TreeSet<>(comp);

TreeSet<Pair> right = new TreeSet<>(comp);

boolean isOdd = k % 2 == 1;

for (int i=0; i<k; i++) {

addNew(i, nums[i], left, right);

}

int len = nums.length;

double[] res = new double[len - k + 1];

for (int i=0; i<=len-k; i++) {

res[i] = left.size() == right.size() ? ((double) left.last().value + (double) right.first().value) / 2.0 : (double) left.last().value;

if (i == len-k) break;

Pair oldP = new Pair(i, nums[i]);

boolean inLeft = left.remove(oldP);

if (!inLeft) right.remove(oldP);

addNew(i+k, nums[i+k], left, right);

}

return res;

}

private void addNew(int index, int value, TreeSet<Pair> left, TreeSet<Pair> right) {

Pair p = new Pair(index, value);

if (right.size() != 0 && value > right.first().value) {

right.add(p);

} else {

left.add(p);

}

balance(left, right);

}

private void balance(TreeSet<Pair> left, TreeSet<Pair> right) {

while (left.size() > right.size() + 1) {

Pair topLeft = left.pollLast();

right.add(topLeft);

}

while (left.size() < right.size()) {

Pair bottomRight = right.pollFirst();

left.add(bottomRight);

}

}

class Pair {

int index;

int value;

Pair(int i, int v) {

index = i;

value = v;

}

}

public double[] medianSlidingWindow3(int[] nums, int k) {

Comparator<Integer> comp = (i1, i2) -> Integer.compare(i2, i1);

PriorityQueue<Integer> left = new PriorityQueue<>(comp);

PriorityQueue<Integer> right = new PriorityQueue<>();

for (int i=0; i<k; i++) {

if (left.isEmpty() || nums[i] <= left.peek()) {

left.add(nums[i]);

} else {

right.add(nums[i]);

}

if (left.size() < right.size()) {

left.add(right.poll());

} else if (left.size() > right.size() + 1) {

right.add(left.poll());

}

}

int N = nums.length;

double[] res = new double[N-k+1];

for (int i=k; i<=N; i++) {

if (left.size() == right.size() + 1) {

res[i-k] = left.peek() * 1.0;

} else {

res[i-k] = ((long)left.peek() + (long)right.peek()) / 2.0;

}

if (i == N) break;

int toPop = nums[i-k];

int toAdd = nums[i];

if (toAdd <= left.peek()) {

left.add(toAdd);

} else {

right.add(toAdd);

}

if (left.peek() >= toPop) {

left.remove(toPop);

} else {

right.remove(toPop);

}

if (left.size() < right.size()) {

left.add(right.poll());

} else if (left.size() > right.size() + 1) {

right.add(left.poll());

}

}

return res;

}

public static void main(String[] args) {

SlidingWindowMedian480 swm = new SlidingWindowMedian480();

int [] nums = {1, 3, -1, -3, 5, 3, 6, 7};

int [] twos = {2147483647, 2147483647};

System.out.println(Arrays.toString(swm.medianSlidingWindow(nums, 3)));

System.out.println(Arrays.toString(swm.medianSlidingWindow(nums, 4)));

System.out.println(Arrays.toString(swm.medianSlidingWindow(twos, 2)));

}