Fixed Window Extrema

When To Use

Use this when every query is over a fixed-size window and you need the max or min.

Prerequisite: Base Monotonic Deque

Template

for r = 0; r < n; r++:
    push r into monotonic deque
 
    expire indices before r - k + 1
 
    if r >= k - 1:
        answer uses dq.front

Fixed window means the left boundary is implicit: l = r - k + 1.

Problems

Sliding Window Maximum

Problem: return the maximum of every size-k window.

Pattern: fixed window max.

Applied pseudocode:

for r = 0; r < n; r++:
    while dq not empty and nums[dq.back] <= nums[r]:
        pop back
 
    push r
 
    if dq.front <= r - k:
        pop front
 
    if r >= k - 1:
        ans.push(nums[dq.front])

Sliding Window Minimum

Problem: return the minimum of every size-k window.

Pattern: fixed window min.

K Empty Slots

Problem: find the earliest day where two on bulbs have exactly k off bulbs between them.

Pattern: invert to days[], then range-min over the fixed middle window.

Razika

Problem: after sorting, evaluate fixed-length kept windows and their best internal gap.

Pattern: fixed window min over adjacent differences.