```
Given an array of n * m matrix, and a moving matrix window (size k * k), move the window from top left to bottom right at each iteration, find the median number inside the window at each moving
Can you do it better than brutal force method?
void getMedian(int[][] matrix, int k){
print median
}
For matrix
[
[1, 5, 3],
[3, 2, 1],
[4, 1, 9],
]
The moving window size k = 2.
At first the window is at the start of the array like this
[
[|1, 5|, 3],
[|3, 2|, 1],
[4, 1, 9],
]
,get the median (2 + 3) / 2 = 2.5;
then the window move one step forward.
[
[1, |5, 3|],
[3, |2, 1|],
[4, 1, 9],
]
,get the median (2 + 3) / 2 = 2.5
then the window move one step forward again.
[
[1, 5, 3],
[|3, 2|, 1],
[|4, 1|, 9],
]
,get the median (2 + 3) / 2 = 2.5
then the window move one step forward again.
[
[1, 5, 3],
[3, |2, 1|],
[4, |1, 9|],
]
,get the median (1 + 2) / 2 = 1.5
```

Treat it as a stream: when moving the window smartly k elemts leave the window and k enter. Let's suppose we do partition the first k*k window, to find the median, this takes O(k*k). Then I move right, I will know of the k elements I remove and I get k elements to add. If I only added k elements I could simply use two heaps and kind of calculate a "running" mean. But now, I have to remove k elements as well. So I'd need a heap where I can find and remove a specific element. One can do this with a custom bin heap implementation and use a HT as index.

- Chris September 19, 2017Let's see, the heaps are O(k^2) in size. Initial creation is O(k*k*lg(k)). Then for each of the (n-k)^2 moves it takes 2*lg(k). So O(k^2*lg(k^2)+n^2*lg(k)). That is O(n^2*lg(k)). Instead of O(n^2*n^2) or O(n^4*lg(n^2)) depending on brute force approach.

I think decent, improvement possible by Fibonacci heaps, but either way a bit ugly to code due to the special requirement on having a trackable heap element that can be referenced (indexes) by hash table.