# What is the need of such a complicated solution using Deque?

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

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

}

for(int i = windowSize; i < arr.length; ++i) {

// 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

}

// Adding the max number of the current window in the result

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<>();
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];
}
}
}
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.

1 Like

I agree with all of it and even if the window size is the entire array the inner loop can be avoided be its just max element of the array so it should be O(n) .

1 Like

https://www.youtube.com/watch?v=m-Dqu7csdJk Watch this and you will know that it’s the best solution with o(n) complexity.

The following solution is also valid but I cannot comment on the complexity:

vector<int> find_max_sliding_window(vector<int>& v, int window_size)
{
vector<int> result;
int n = v.size() - window_size;
for (auto i=0; i <= n ; ++i)
{
//cout << "i = " << i << endl;
int* pFirst = &v[i];
int* pLast = &v[i+window_size];
int* pMaxVal = max_element(pFirst,pLast);
result.push_back(*pMaxVal);
//cout << *pMaxVal << endl;
}
return result;
}
1 Like

I also found the code solution to be quite long but after reading through carefully and reviewing the code, it is a great exercise.

The provided solution seems complicated to me. Perhaps the reason it is provided is because it is optimal, I am unsure. I agree there is educational value to reviewing it. Here is my solution:

let findMaxSlidingWindow = function(arr, window_size) {
var result = [];

const length = arr.length + 1;

let startIndex = 0;
let endIndex = window_size;

while (endIndex < length) {

let subArr = arr.slice(startIndex, endIndex);
result.push((Math.max(...subArr)));
startIndex += 1;
endIndex += 1;
console.log(endIndex);

};

return result;
};
1 Like

I am also wondering why is the deque solution is better than ust finding max() in window?

def find_max_sliding_window(arr, window_size):
result = []
left=0
right = left + window_size
while right <= len(arr):
result.append(max(arr[left:right]))
left += 1
right = left + window_size
return result

Would be great to have a better explanation in the lesson