Stacks and Monotonic Structures
A monotonic structure that also expires
The window from Unit 3 meets the discard rule from this one. This is why the problem waited.
Why this problem was held back
This is the sliding-window problem that Unit 3 skipped. A window slides across an array and you must report an extreme value for every position it occupies.
Recomputing from scratch is O(n times k). A window cannot roll an extreme the way it rolls a sum, because when the current extreme leaves the window there is nothing stored to fall back on. The missing piece is the monotonic discard rule from this unit.
Why it works
Who can still be the answer
Take two positions inside the window, one older and one newer. If the newer one holds a value at least as extreme as the older one, the older one is finished. It will leave the window no later than the newer one, and while both are present the newer one wins.
So the only candidates worth keeping are those in decreasing order of value from oldest to newest. That is a monotonic sequence, exactly as before, and the front of it is the current answer.
Key idea
Why a deque and not a stack
Two different removals are needed and they happen at opposite ends. New arrivals discard weaker candidates from the back, which is the monotonic rule. Candidates that have slid out of the window are discarded from the front, which is expiry.
A stack only opens at one end, so this needs a structure that opens at both. collections.deque gives O(1) append, pop, appendleft, and popleft, which is exactly the four operations required.
Tip
Store indexes, not values
Expiry is about position, so the deque holds indexes. A value alone cannot tell you whether it has slid out of the window.
The front has expired when its index is no longer inside the current window. With a window of width k ending at right, the window starts at right - k + 1, and any index below that is gone.
Gotcha
The order of the three steps
Each iteration does three things and the order matters. Discard weaker candidates from the back, then append the new index, then expire the front, then read the answer once the window is full.
Expiring before appending also works. What breaks is reading the answer before expiring, which can report a value that has already left the window. Whenever a loop has several bookkeeping steps, write down the state you want to be true at the moment you read the answer, and order the steps to make it so.
Cost
Linear, for the usual reason
Every index enters the deque once and leaves once, whether it leaves from the back as a discarded candidate or from the front as an expired one. So all the removals together are O(n) and the whole scan is O(n) time.
The deque holds at most one entry per window position, so the space is O(k). That is the fourth appearance of this amortized argument, and by now it should be a reflex.
Build the piece first
The lab below asks only for the maintenance rules, with no windowing around them. Get those right in isolation, then the problem is mostly assembling them into a loop.
Deque maintenance
Build the two rules on their own. push_candidate adds an index to the back of a deque of indexes, first discarding from the back every index whose value is smaller than the incoming one, and returns the deque. expire_front removes front indexes that have fallen outside a window starting at window_start, and returns the deque. front_value reports the value at the front, or None when empty.
Tests
values = [1, 3, -1, -3, 5]
candidates = deque()
for index in range(4):
push_candidate(candidates, values, index)
print(list(candidates))
print(front_value(candidates, values))
expire_front(candidates, 2)
print(list(candidates), front_value(candidates, values))
push_candidate(candidates, values, 4)
print(list(candidates), front_value(candidates, values))
print(front_value(deque(), values))Output
Run the tests when you are ready.
Sliding Window Maximum
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.