# My space-saving Java solution

• Most solution uses two `PriorityQueue`, which uses a large space.
In fact, to solve this problem, we just need a sorted array through which we can add, delete, and insert a element in a specific position which make the array is still in ascending( or descending) order. So, we can use `ArrayList` to define a new ADT, called `SortedArray`, which meets out needs. It is quite simple. Following is the code:

``````class SortedArray{

List<Integer> array;
SortedArray(){
array = new ArrayList<Integer>();
}
// following method could be optimized by Binary Search, whose run time is O(logn)
int i = array.size()-1;
while(i>=0&&array.get(i)>val) i--;
}
void delete(int val){
array.remove((Integer)val);
}
int get(int val){
return array.get(val);
}
}
``````

By using this `SortedArray`, we can maintain a ordered array when add, delete, or insert a value and its space use is CONSTANT. And time complexity for the solution could be optimized to O(n*logn). Here is the total solution:

``````public class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length < 1 || k < 1) return null;
int len = nums.length, i = 0;
double[] res = new double[len-k+1];
SortedArray array = new SortedArray();
while(i<len){
if(i-k+1>0)
array.delete(nums[i-k]);
if(i-k>=0){
if(k % 2 == 0)
res[i-k] = array.get((k>>>1)-1)/2.0 + array.get(k>>>1)/2.0;
else
res[i-k] = array.get(k>>>1);
}
}
return res;

}

class SortedArray{

List<Integer> array;

SortedArray(){
array = new ArrayList<Integer>();
}

int i = array.size()-1;
while(i>=0&&array.get(i)>val) i--;
}

void delete(int val){
array.remove((Integer)val);
}

int get(int val){
return array.get(val);
}
}
}
``````

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