Busiest hour in each k-hour span

Sliding window Senior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Fill the blank

Fill the blank so the front of the deque is always the span maximum.

Python 3.13

from collections import deque
counts, k = [1, 3, -1, -3, 5, 3, 6, 7], 3
dq: deque[int] = deque()
out = []
for i, c in enumerate(counts):
    while dq and counts[dq[-1]] ____ c:
        dq.pop()
    dq.append(i)
    if dq[0] <= i - k:
        dq.popleft()
    if i >= k - 1:
        out.append(counts[dq[0]])
print(out)

Options<=>===

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A <=

Right: an older count that is not bigger can never be a future maximum.

Popping weaker candidates from the back keeps the deque in decreasing order, so its front is the answer for each span.

Why not the others?

B >=. That throws away the larger, more useful candidates.
C ==. Only removing equal values leaves smaller ones that break the order.

30-second answer

Keep a deque of hour indices whose counts are decreasing from front to back. For each new hour, pop smaller counts from the back (they can never be a maximum again), push the hour, and drop the front if it has left the span. The front is always the span's maximum. Each index is pushed and popped once: O(n). The deque holds at most k indexes, so it takes O(k) extra space.

Practise saying it · 60 s. No recording, just a timer

Explain the monotonic deque for span maximums.

Say your answer out loud, then check which of these points you covered:

Deque of indices, decreasing counts
Pop smaller from the back
Evict the front when it leaves

Deep dive

The deque holds candidates, not the whole window; anything smaller and older than a new value is useless.

Storing indices (not values) lets you tell when the front has slid out of the span.

A heap with lazy deletion is O(n log n); the deque is the expected O(n) answer.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

from collections import deque


def span_maximums(counts: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    out: list[int] = []
    for i, c in enumerate(counts):
        while dq and counts[dq[-1]] <= c:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(counts[dq[0]])
    return out

Common mistakes

Storing values, then not knowing when to evict the front.
Popping with < vs <=: both are correct here; just be consistent.

Senior take & follow-ups

Explain why popping smaller items is safe: the new item is larger and will stay in every future span longer.

Follow-up questions

Think of your answer first, then open the hint.

What about the minimum of each span?
Show hint
Same deque with the comparison flipped.
Where else is a monotonic deque used?
Show hint
Shortest run with a sum at least a goal when values can be negative, and some DP speed-ups.

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.