Skip to main content
← PROBLEMS / CODING-ALGORITHM
An end-to-end domain learning journey

Sliding Window Maximum with
a Monotonic Deque.

A real-time SLA monitor ingests 500,000 latency samples/sec per shard and must emit the exact rolling maximum latency over the last k = 10,000 samples (and in a variant, over a W = 5,000 ms time window). The current implementation uses a max-heap (PriorityQueue / heapq) with lazy deletion, which grows beyond 100k stale nodes during bursts and triggers p99 spikes and GC pauses. Design a strict O(1) amortized-per-event sliding window maximum engine.
Start the journey5 stages
Loading diagram…
Sliding Window Maximum with a Monotonic Deque architecture sketch diagram
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

A real-time SLA monitor ingests 500,000 latency samples/sec per shard and must emit the exact rolling maximum latency over the last `k = 10,000` samples (and in a variant, over a `W = 5,000 ms` time window). The current implementation uses a max-heap (`PriorityQueue` / `heapq`) with lazy deletion, which grows beyond `100k` stale nodes during bursts and triggers `p99` spikes and GC pauses. Design a strict `O(1)` amortized-per-event sliding window maximum engine.

From patterns to decisions.

A real-time SLA monitor ingests 500,000 latency samples/sec per shard and must emit the exact rolling maximum latency over the last `k = 10,000` samples (and in a variant, over a `W = 5,000 ms` time window). The current implementation uses a max-heap (`PriorityQueue` / `heapq`) with lazy deletion, which grows beyond `100k` stale nodes during bursts and triggers `p99` spikes and GC pauses. Design a strict `O(1)` amortized-per-event sliding window maximum engine.

01
CODING-ALGORITHM · STAGE 01L4 · FUNDAMENTALS

A lazy-deletion heap never pops.

A lazy-deletion heap never pops expired smaller items until they reach the root, growing to O(N); storing indices lets the deque detect window expiry in O(1).

ChoiceWhat it buysWhat it costs
Trade-off 1Deque achieves O(N) time and <= k space, whereas heap takes O(N log k) time and up to O(N) space.

Step 1

Trace [100, 99, 98, ...] in a lazy-deletion heap: 100 stays at root for k steps while 99..1 accumulate below.

Step 2

Show that storing (index, value) allows dq[0][0] <= i - k.

Alternative 1

For arbitrary element deletion (non-sliding), a TreeMap or indexed heap is needed.

Failure Mode 1

Using Python list.pop(0) instead of deque.popleft() degrades to O(N*k).

# Monotonically decreasing input [1000, 999, 998, ..., 1] with k=10:
# Lazy heap holds all 1000 nodes until 1000 expires; deque holds at most 10.
02
CODING-ALGORITHM · STAGE 02L5 · APPLIED DESIGN

Use collections.

Use collections.deque storing (index_or_ts, value) with popleft() for window expiry and pop() for monotonic dominance.

ChoiceWhat it buysWhat it costs
Trade-off 1Strict O(N) total time across N events and <= k memory.

Step 1

Evict expired front elements (while loop for time-based, if for count-based).

Step 2

Pop back elements <= val to preserve strict decreasing order.

Step 3

Append (key, val) and return dq[0][1].

Alternative 1

In Java, use a primitive long[] / double[] circular ring buffer to avoid GC allocation at 500k/s.

Failure Mode 1

Using if instead of while in push_time leaks expired elements when multiple events share a timestamp.

from collections import deque

class SlidingWindowMax:
    def __init__(self, window_size: int) -> None:
        self.k = window_size
        self.dq: deque[tuple[int, float]] = deque()
        self.idx = 0

    def push_count(self, val: float) -> float:
        if self.dq and self.dq[0][0] <= self.idx - self.k:
            self.dq.popleft()
        while self.dq and self.dq[-1][1] <= val:
            self.dq.pop()
        self.dq.append((self.idx, val))
        self.idx += 1
        return self.dq[0][1]

    def push_time(self, ts_ms: int, val: float) -> float:
        cutoff = ts_ms - self.k
        while self.dq and self.dq[0][0] <= cutoff:
            self.dq.popleft()
        while self.dq and self.dq[-1][1] <= val:
            self.dq.pop()
        self.dq.append((ts_ms, val))
        return self.dq[0][1]
03
CODING-ALGORITHM · STAGE 03L6 · SCALE & TRADE-OFFS

Using <= evicts older equal.

Using <= evicts older equal maxima immediately because the newer identical value will stay in the window longer—keeping deque size smaller.

ChoiceWhat it buysWhat it costs
Trade-off 1`<=` minimizes memory on flat plateaus; use `<` only if you specifically need the *oldest* index of a tied maximum.

Compare `[5, 5, 5]` with `k=3`

< keeps all three (0,5),(1,5),(2,5), while <= keeps only (2,5).

Alternative 1

Two-stack queue max algorithm if you prefer a purely functional / immutable approach.

Failure Mode 1

None for max value; only affects index tie-breaking.

# With <= on [5, 5, 5]: deque holds [(2, 5)] (len=1)
# With <  on [5, 5, 5]: deque holds [(0, 5), (1, 5), (2, 5)] (len=3)
04
CODING-ALGORITHM · STAGE 04L6 · SCALE & TRADE-OFFS

Implementation & Guardrails (4).

Pre-aggregate incoming events into fixed-width time buckets (e.g., 10 ms tumbling buckets) and run the monotonic deque over those 500 buckets instead of raw events.

ChoiceWhat it buysWhat it costs
Trade-off 1Caps memory at O(W / bucket_ms) with +-10 ms boundary granularity.

Step 1

Bucket timestamps via bucket_ts = (ts_ms // 10) * 10 and track max per bucket.

Step 2

Feed completed/active buckets into the monotonic deque, capping memory at 5000 / 10 = 500 entries.

Alternative 1

Hard-cap deque length and shed oldest samples during extreme floods.

Failure Mode 1

Unbounded raw-event deque OOMing during DDoS or retry storms.

# 10 ms bucketing bounds 5,000 ms window to <= 500 deque entries regardless of QPS!
05
CODING-ALGORITHM · STAGE 05L7 · STAFF / PRINCIPAL

Run one local monotonic deque.

Run one local monotonic deque per partition, emit each partition's (bucket_ts, local_max) to an aggregator, and take max across the 16 partition maxima.

ChoiceWhat it buysWhat it costs
Trade-off 1Reduces cross-network fan-in by 500,000x while preserving exactness per aligned time bucket.

Step 1

Exploit associativity of max(A ∪ B) = max(max(A), max(B)).

Step 2

Aggregate 16 local bucket maxima in O(16) instead of centralizing 8M raw events/sec.

Alternative 1

Apache Flink sliding window with AggregateFunction.

Failure Mode 1

Clock skew across partitions causing misaligned bucket boundaries; use event-time watermarks.

global_max = max(partition_maxes.values())  # 16 values instead of 8M events/s

Theory & Tips and Tricks

Practical heuristics & interview traps

  • 01Interview anchor: Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.
  • 02Trade-off tip: <= minimizes memory on flat plateaus; use < only if you specifically need the oldest index of a tied maximum.
  • 03Watch out for: Unbounded raw-event deque OOMing during DDoS or retry storms.
Behavioral Progression · Sliding Window Maximum Monotonic Deque

Sliding Window Maximum Monotonic Deque — Normal → Load / Fault → Recovery

Send Request
1. Normal Request Ingress
Traffic: 1x baseline · Latency (p99): 4 ms
Process State
2. Core Execution & State Lookup
Traffic: 1x baseline · Latency (p99): 9 ms
Inject 10x Spike
3. Scale Spike / Failure Injection
Traffic: 10x burst · Latency (p99): 185 ms

Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.

Synthesis / One connected design

Putting Sliding Window Maximum with a Monotonic Deque Together

Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.

A candidate architecture, not a universal answer

Putting Sliding Window Maximum with a Monotonic Deque Together

Step 1
Step 2
Step 3
  1. Evict expired front elements (while loop for time-based, if for count-based).
  2. Pop back elements <= val to preserve strict decreasing order.
  3. Append (key, val) and return dq[0][1].
Pre-aggregate incoming events into fixed-width time buckets (e.g., 10 ms tumbling buckets) and run the monotonic deque over those 500 buckets instead of raw events.
Interview Readiness Check

Pre-aggregate incoming events into fixed-width time buckets (e.g., 10 ms tumbling buckets) and run the monotonic deque over those 500 buckets instead of raw events.

Walk through bottlenecks, back-of-the-envelope math, and failure recovery.

Practice / Explain the consequences

Make the trade-off yourself.

Practice Check

Test your understanding

Question 1 of 3

When is ACID Transaction Fundamentals the right default for a production team?

Key takeaway

Sliding Window Maximum with a Monotonic Deque

Store indices in a monotonic decreasing deque, evicting expired front indices and smaller back indices so every element is pushed and popped at most once.