In this algorithm, since for every element in array (size n), we need to compare it with the element in window (size w). So in the worst case, is the time complexity n(w*n)?
Thanks!
The complexity does seem to be O(n*w) at first, but here is the tricky part. Each element in the array is added and popped from the window exactly once. So for n iterations, even if we push and pop elements in a nested loop, those elements will never be considered again. So in the end, it adds up to O(2n) because of the 2 operations on each element. This turns the complexity to O(n).