Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Monotonic deques: maintain a sliding minimum in linear time

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A monotonic deque keeps candidate indices in increasing value order for a sliding-window minimum. When a new value arrives, remove older candidates from the back while their values are greater than or equal to it; they cannot become the minimum before the newer equal-or-smaller value expires. Remove indices from the front when they leave the window. The front then identifies the minimum. Each index enters and leaves at most once, so all windows together cost O(n) time and O(w) extra space for window width w. The tie rule here prefers the newer equal value.

Operational case

A sensor receives delay readings 47, 31, 26, 58, 19, and 42. A three-reading window produces minima 26, 26, 19, and 19. A heap could also track candidate values but would need a stale-index policy and O(log w) insertion; rescanning each window costs O(nw). The deque's removal logic discards values that can never win a future window. If the window width changes on every request, precomputation and state ownership need a different contract.

Working Python program

python
from collections import deque

readings = [47, 31, 26, 58, 19, 42]
window_width = 3
candidates = deque()
minimums = []
for reading_index, delay in enumerate(readings):
    while candidates and candidates[0] <= reading_index - window_width:
        candidates.popleft()
    while candidates and readings[candidates[-1]] >= delay:
        candidates.pop()
    candidates.append(reading_index)
    if reading_index + 1 >= window_width:
        minimums.append(readings[candidates[0]])
print(minimums)

Output

Output
[26, 26, 19, 19]

Time, space, and tradeoff

The loop processes n readings and stores at most w candidate indices. Each index is appended once and removed at most once, giving O(n) total time despite the nested while loops. The result list itself needs O(n - w + 1) space. Validate 1 <= w <= n before running; zero width makes the expiration rule meaningless. If readings are corrected retroactively, this one-pass stream state cannot repair old emitted windows without replay or a separate indexed structure.

Common Mistakes

  • Do not mistake nested loops here for O(nw) total work.
  • Do not store values alone when expiry requires their indices.
  • Do not accept a zero-width window.

Connected lessons

Apply it: Project: design a versioned warehouse index and Advanced structure contracts.

Two-stack window aggregation: keep FIFO order under a monoid adds a distinct structure contract to compare.

Exponential histograms: estimate failures in a recent event window adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details