In the second case, every time the window moves forward, the new element is smaller than all the other elements in the deque, so the pop_back() operation is only performed once in every subsequent step, to remove the element which does not fall in the window anymore. So, again the time complexity is O(n)O(n).
In the third case, the same behaviour is repeated as in the second case, so the time complexity is O(n)O(n) here too.
In the third case, the same behaviour is repeated as in the second case, so the time complexity is O(n)O(n) here too.
Course: https://www.educative.io/courses/grokking-coding-interview-patterns-cpp
Lesson: Solution: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in C++
