The sliding window maximum problem is a classic example where a naive approach leads to inefficient solutions, but clever use of data structures can dramatically improve performance.
The naive approach would be to examine each window of size k and find its maximum using a nested loop - this gives us O(nk) time complexity. For large arrays with large window sizes, this becomes prohibitively slow.
The key insight is that we don't need to recalculate everything when the window slides. As we move from one window to the next, we're only removing one element from the left and adding one to the right. If we could maintain a data structure that tracks potential maximums efficiently, we could reduce this to O(n) time.
A deque (double-ended queue) is perfect for this. The strategy is to maintain a deque of indices (not values) with two important properties:
When processing a new element, we remove indices from the back of the deque if their values are smaller than or equal to the current element. Why? Because the current element is more recent and at least as large, so those older elements can never be the maximum of any future window.
This technique, sometimes called a "monotonic deque," ensures each element is added and removed at most once, giving us O(1) amortized time per element.
1from collections import deque
2
3def find_max_in_subarrays(arr, window_size):
4 """Example of monotonic deque pattern"""
5 dq = deque() # stores indices
6
7 for i, val in enumerate(arr):
8 # Remove indices outside window
9 while dq and dq[0] <= i - window_size:
10 dq.popleft()
11
12 # Remove smaller elements from back
13 while dq and arr[dq[-1]] <= val:
14 dq.pop()
15
16 dq.append(i)
17
18 if i >= window_size - 1:
19 print(f"Max in window ending at {i}: {arr[dq[0]]}")