The deque stores indices in increasing order of their values (for finding minimum). When you process position :
Remove indices from the front if they're outside the window .
The front index gives you the minimum value in the window.
Remove indices from the back while their values are .
Add to the back. Each index enters once and leaves once. Total time:
Time complexity: amortized for all operations combined.
Space complexity: for the deque.