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.

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.

1from collections import deque2 3candidates = deque()4candidates.append(3)          # add at the back5candidates.appendleft(9)      # add at the front6print(candidates, candidates[0], candidates[-1])7 8candidates.popleft()          # remove the front, O(1)9candidates.pop()              # remove the back, O(1)10print(candidates)

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.

Code lab· 25 min

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.

solution.py

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 tests to see output.

Problem· 35 min

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.

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.

1from collections import deque2 3candidates = deque()4candidates.append(3) # add at the back5candidates.appendleft(9) # add at the front6print(candidates, candidates[0], candidates[-1])7 8candidates.popleft() # remove the front, O(1)9candidates.pop() # remove the back, O(1)10print(candidates)

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))