I don’t understand why do we need to use a Deque for this problem? The algorithm seems unncessarily complicated -
public static ArrayDeque<Integer> findMaxSlidingWindow(int[] arr, int windowSize) {
ArrayDeque<Integer> result = new ArrayDeque<>(); // ArrayDeque for storing values
Deque<Integer> list = new LinkedList<Integer>(); // creating a linked list
if(arr.length > 0) {
if( arr.length < windowSize) // Invalid State
return result;
for(int i = 0; i < windowSize; ++i) {
// Removing last smallest element index
while(!list.isEmpty() && arr[i] >= arr[list.peekLast()]){
list.removeLast();
}
// Adding newly picked element index
list.addLast(i);
}
for(int i = windowSize; i < arr.length; ++i) {
result.add(arr[list.peek()]);
// Removing all the elements indexes which are not in the current window
while((!list.isEmpty()) && list.peek() <= i-windowSize)
list.removeFirst();
// Removing the smaller elements indexes which are not required
while((!list.isEmpty()) && arr[i] >= arr[list.peekLast()])
list.removeLast();
// Adding newly picked element index
list.addLast(i);
}
// Adding the max number of the current window in the result
result.add(arr[list.peek()]);
return result; // returning result
}
else
return result;
}
Why not just make a simple pass through the array and calculate the maximum number in each window?
public static ArrayDeque<Integer> findMaxSlidingWindow(int[] arr, int windowSize) {
ArrayDeque<Integer> result = new ArrayDeque<>();
//Write your code
int max;
for(int i = 0; i <= (arr.length-windowSize); i++) {
max = arr[i];
for(int k = i; k < (i+windowSize); k++) {
if(arr[k] >= max) {
max = arr[k];
}
}
result.add(max);
}
return result;
}
The inner for loop only runs a constant ( = windowSize) number of times for each iteration of the outer loop, so total complexity is still O(n)
. It can be O(n^2
) at the worst, if you consider the windowSize to be the entire array.