# Java solution using two PriorityQueues

• The idea is similar to 295.Find Median from Data Stream. I used two priority queues to solve this problem. To avoid max integer value overflow, Long data type is used here.

``````class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
PriorityQueue<Long> small = new PriorityQueue<>();
PriorityQueue<Long> large = new PriorityQueue<>();

double[] res = new double[nums.length - k + 1];
int m = k / 2;
for(int i = 0; i < k; i++){
insert(nums[i], small, large);
}

res[0] = findMedian(small, large);
for(int j = k; j < nums.length; j++){
remove(nums[j - k], small, large);
insert(nums[j], small, large);
res[j - k + 1] = findMedian(small, large);
}
return res;
}

public void insert(long n, PriorityQueue<Long> small, PriorityQueue<Long> large){
if(large.size() < small.size()){
}
}
public void remove(long n, PriorityQueue<Long> small, PriorityQueue<Long> large){
if(n < findMedian(small, large)){
small.remove(-n);
}
else{
large.remove(n);
}
}
public double findMedian(PriorityQueue<Long> small, PriorityQueue<Long> large){
if(large.size() > small.size()){
return large.peek() * 1.0;
}
else{
return (large.peek() - small.peek()) / 2.0;
}
}
}
``````

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