Java solution using two PriorityQueues

• Almost the same idea of `Find Median from Data Stream` https://leetcode.com/problems/find-median-from-data-stream/

1. Use two `Heaps` to store numbers. `maxHeap` for numbers smaller than current median, `minHeap` for numbers bigger than and `equal` to current median. A small trick I used is always make size of `minHeap` equal (when there are `even` numbers) or 1 element more (when there are `odd` numbers) than the size of `maxHeap`. Then it will become very easy to calculate current median.
2. Keep adding number from the right side of the sliding window and remove number from left side of the sliding window. And keep adding current median to the result.
``````public class Solution {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
new Comparator<Integer>() {
public int compare(Integer i1, Integer i2) {
return i2.compareTo(i1);
}
}
);

public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length - k + 1;
if (n <= 0) return new double[0];
double[] result = new double[n];

for (int i = 0; i <= nums.length; i++) {
if (i >= k) {
result[i - k] = getMedian();
remove(nums[i - k]);
}
if (i < nums.length) {
}
}

return result;
}

if (num < getMedian()) {
}
else {
}
if (maxHeap.size() > minHeap.size()) {
}
if (minHeap.size() - maxHeap.size() > 1) {
}
}

private void remove(int num) {
if (num < getMedian()) {
maxHeap.remove(num);
}
else {
minHeap.remove(num);
}
if (maxHeap.size() > minHeap.size()) {
}
if (minHeap.size() - maxHeap.size() > 1) {
}
}

private double getMedian() {
if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;

if (maxHeap.size() == minHeap.size()) {
return ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
}
else {
return (double)minHeap.peek();
}
}
}
``````

• Complexity is only O(nk), right?

• @StefanPochmann I guess it's O(N lgK)? As each add() and remove() operation takes lgK time? And there are N elements to operate.
getMedian() is O(1).

• @shawngao The documentation says `remove(Object)` takes linear time.

• @StefanPochmann You are right. Then the overall runtime complexity is O(nk).

• @shawngao It's O(nk), not O(nlogk).

• Time complexity is O(nlogk) if using Treemap instead of heap.

• @dtcxzch11 but you need to take care of the duplicates and it is really annoying

• Thank you @shawngao for this solution. I have made the code more concise by removing the duplicate parts.
Thank you @StefanPochmann for your suggestions. I have included them.

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

public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length - k + 1;
if (n <= 0) return new double[0];

double[] result = new double[n];

for (int i = 0; i <= nums.length; i++) {
if (i >= k){
result[i - k] = getMedian();
remove(nums[i - k]);
}
if(i < nums.length){
}
}
return result;
}

(num < getMedian() ? maxHeap : minHeap).add(num);
resizeHeaps();
}

private void remove(int num) {
(num < getMedian() ? maxHeap : minHeap).remove(num);
resizeHeaps();
}

private void resizeHeaps(){
if (maxHeap.size() > minHeap.size()) {
}
if (minHeap.size() - maxHeap.size() > 1) {
}
}

private double getMedian() {
if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;
else if (maxHeap.size() == minHeap.size()) {
return ((double) maxHeap.peek() + (double) minHeap.peek()) / 2.0;
}
else {
return (double) minHeap.peek();
}
}
}``````

• @chaitanya0411 If you like concise, you could also do `(num < getMedian() ? maxHeap : minHeap).add(num);`.

• Actually you can just implement `minHeap` and `maxHeap` by your self, and using a `HashMap` to access the position of need-to-removed node, in this way, you can achieve the time complexity in O(nlogk).

• @dtcxzch11 but you need to take care of the duplicates and it is really annoying

It's not too bad. See my solution using two Tree Sets.

• @shawngao Fails for input [1] , k = 1

• @thepha3drus Really? It works for me.

``````Custom Testcase
[1]
1

[1.00000]

[1.00000]
``````

• Well, this is O(nk), same as brute force method's time complexity. And brute force method even beats this on space complexity.

• My answer using TreeSet to implement heaps, similar to the answer of @shawngao.
When writing the compareTo method in Node class, I discovered that if simply write code like this would not pass the last test case, because Integer.MIN_VALUE - Integer.MAX_VALUE returns 1 which is a postive value.
It took some time for me to find the mistake, so I post this to prevent you guys from making the same mistake as me.

`````` public int compareTo(Node other) {
if (this.val != other.val) {
return this.val - other.val;
} else {
return this.index - other.index;
}
}
``````
``````class Node implements Comparable<Node>{
public int index;
public int val;

public Node(int index, int val) {
this.index = index;
this.val = val;
}

@Override
public int compareTo(Node other) {
if (this.val != other.val) {
return new Integer(this.val).compareTo(new Integer(other.val));
} else {
return this.index - other.index;
}
}
}

public class Solution {

TreeSet<Node> minHeap = new TreeSet<>();
TreeSet<Node> maxHeap = new TreeSet<>();

public double[] medianSlidingWindow(int[] nums, int k) {
List<Double> list = new ArrayList<>();

if (nums == null || nums.length == 0 || k > nums.length) {
return new double[list.size()];
}

for (int i = 0; i < k-1; i++) {  //add k-1 numbers into two heaps
}

for (int i = k-1; i < nums.length; i++) {
remove(new Node(i-k+1, nums[i-k+1]));
}

double[] result = new double[list.size()];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(i);
}
return result;
}

if (maxHeap.size() < minHeap.size()) {
}

if (maxHeap.size() - minHeap.size() > 1) {
}
}

public void remove(Node n) {
if (minHeap.contains(n)) {
minHeap.remove(n);
} else {
maxHeap.remove(n);
}

if (maxHeap.size() < minHeap.size()) {
}

if (maxHeap.size() - minHeap.size() > 1) {
}
}

public double getMedian() {
if (minHeap.size() == maxHeap.size()) {
return minHeap.first().val/2.0 + maxHeap.last().val/2.0;
} else {
return maxHeap.last().val;
}
}
}
``````

• Same idea. Simple Version.

``````public double[] medianSlidingWindow(int[] nums, int k) {
double[] result = new double[nums.length - k + 1];
PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> right = new PriorityQueue<>();

for(int i = 0; i < nums.length; i++) {
if(left.size() <= right.size()) {
} else {
}

if(left.size() + right.size() == k) {
double median;
if(left.size() == right.size()) {
median = (double) ((long)left.peek() + (long)right.peek()) / 2;
} else {
median = (double) left.peek();
}

int start = i - k + 1;
result[start] = median;
if(!left.remove(nums[start])) {
right.remove(nums[start]);
}
}
}
return result;
}``````

• @GardenAAA Same idea as yours, nice looking code, upvoted

• Cleaner Version:

``````public class Solution {
Queue<Integer> minHeap = new PriorityQueue<>();
Queue<Integer> maxHeap = new PriorityQueue<>(1, Collections.reverseOrder());

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

for(int i = 0; i < nums.length; ++i) {
if (i - k >= 0) {
removeNum(nums[i - k]);
}
if (i - k + 1 >=0) {
medians[i- k + 1] = getMedian();
}
}

return medians;
}

if (minHeap.isEmpty()) {
minHeap.offer(n);
return;
} else if (minHeap.peek() <= n) {
minHeap.offer(n);
} else {
maxHeap.offer(n);
}
rebalance();
}

private void removeNum(int n) {
if (minHeap.peek() <= n) {
minHeap.remove(n);
} else {
maxHeap.remove(n);
}
rebalance();
}

private void rebalance() {
if (minHeap.size() - maxHeap.size() > 1) {
maxHeap.offer(minHeap.poll());
} else if (maxHeap.size() > minHeap.size()) {
minHeap.offer(maxHeap.poll());
}
}

private double getMedian() {
return minHeap.size() == maxHeap.size() ? ((double)minHeap.peek() + maxHeap.peek()) / 2 : minHeap.peek();
}
}
``````

• ``````    public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length;
double[] res = new double[n - k + 1];
PriorityQueue<Integer> minHeap = new PriorityQueue();
PriorityQueue<Integer> maxHeap = new PriorityQueue(Collections.reverseOrder());

int i = 0;
for(; i < Math.min(k, n); i++){
if(minHeap.size() != maxHeap.size()){
minHeap.offer(nums[i]);
maxHeap.offer(minHeap.poll());
} else {
maxHeap.offer(nums[i]);
minHeap.offer(maxHeap.poll());
}
}

int j = 0;
for(; i < n; i++){
if(minHeap.size() == maxHeap.size()){
res[j] = minHeap.peek() / 2d +  maxHeap.peek() / 2d;
} else {
res[j] = minHeap.peek();
}
if(nums[i - k] >= res[j]){
minHeap.remove(nums[i - k]);
maxHeap.offer(nums[i]);
minHeap.offer(maxHeap.poll());
} else {
maxHeap.remove(nums[i - k]);
minHeap.offer(nums[i]);
maxHeap.offer(minHeap.poll());
}
j++;
}

if(minHeap.size() == maxHeap.size()){
res[j] = minHeap.peek() / 2d +  maxHeap.peek() / 2d;
} else {
res[j] = minHeap.peek();
}
return res;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.