Suppose a stream of measurements arrives one value at a time, and we want the minimum of the most recent values after every arrival. Rechecking all entries for every window takes comparisons over a length- sequence. A monotone deque can answer all these particular range queries in total work.
The speedup comes from remembering which old values can still matter. Some candidates expire because they leave the window. Others become permanently unnecessary because a later value is no larger and stays available at least as long. These are different reasons for deletion, and a correct implementation must handle both.
State exactly which queries are being answered
Definition 12.1.1
(Fixed-width windows and a minimum witness)
Let be values with a consistent total order, and choose an integer . For every right endpoint , the full window is
We will return both and an index attaining it. If several indices attain the minimum, our default policy returns the latest one. A later variant returns the earliest one instead.
A deque allows insertion and removal at both ends. Our deque stores indices, not just values. Indices tell us which candidates have left the window and let us state the duplicate policy precisely. At any step the front is the oldest retained index and the back is the newest.
The sequence of queries is part of the problem: both endpoints move forward, one position at a time. A structure designed for these windows does not automatically answer arbitrary intervals presented in arbitrary order. Values such as floating-point NaN, whose comparisons do not obey the assumed total order, are outside the contract used here.
Why a later no-larger value makes an earlier one unnecessary
Lemma 12.1.2
(Dominance lemma)
Let with . Every fixed-width window with right endpoint that contains also contains , and . Hence is not needed to find the minimum value of any such window, and under the latest-witness policy it is never the preferred witness.
Proof X-ray
Dominance preserves every later window that could need the old index
Suppose and . Consider a window produced after has arrived whose right endpoint is . If it contains , then
so it also contains . The later value is no larger, and it expires later than . Therefore is never necessary to obtain the minimum value of any such future window.
If equality holds and we want the latest minimizing index, is also the preferred witness. We may discard immediately. If we require the earliest witness, equality alone does not justify deleting ; only a strictly smaller later value does.
This is a statement about future windows after the new index has arrived. It does not change an answer that was already required for an earlier window. We emit each window's answer when its right endpoint is processed, before future arrivals can remove its witnesses.
Common mistake
(Emitting an answer after the next arrival)
Take and . The window ending at is with minimum at index 0. If its answer is read only after index 2 has been processed, index 0 has expired and the new value has removed index 1, so the front is index 2 and the reported value is , which is not in the window. Read the front immediately after processing .
Maintain increasing indices and increasing values
For the latest-minimum policy, process each arriving index in this order:
- Remove front indices smaller than the new left endpoint . They have expired.
- While the back index has , remove it. The new index dominates it.
- Append at the back.
- Once , emit the front index and its value.
After the insertion, retained indices increase strictly from front to back, because every new index is larger than all earlier ones. Their values also increase strictly: the second step removes all back values that are at least the new value, leaving a smaller last value before appending.
Theorem 12.1.3
(Correctness of the monotone deque)
With the latest-minimum rule, after the arrival of each right endpoint the front of the deque is the latest index attaining in the window .
Proof X-ray
Every active observation still has a retained representative
Use this additional invariant after each insertion: for every active index , some retained index satisfies
An index may represent itself. When a retained back index is removed by a new value, the new index dominates both that old candidate and all indices it represented, by transitivity of the two inequalities. The new index represents itself as well.
When a front candidate expires, it cannot have been the representative of an observation still active: any index it represents is no later than itself, so it would already have expired too. Expiry therefore preserves coverage of active observations.
The front has the smallest value among retained candidates. The retained indices are themselves active, and every other active value has a retained representative no larger than it. Consequently, the front value is exactly the active window's minimum.
There is a small distinction between this minimum-value proof and the tie rule. For the latest witness, no earlier equal candidate survives the arrival of a later equal value. Among current minimum values, the latest one therefore remains. For the earliest-witness variant, keep equal values, making the retained values nondecreasing rather than strictly increasing; the first surviving equal minimum is then the earliest one still in the window.
Trace equality, domination and output separately
Worked example 12.1.4
(Duplicate minima change the witness even when the minimum value stays fixed)
Use and width . The table uses the default rule that removes a back value when it is greater than or equal to the new value. Deque entries are written as index:value pairs.
| Arriving index | Value | Deque after insertion | Full-window answer (index, value) |
|---|---|---|---|
| Not yet a full window | |||
| Not yet a full window | |||
At index 2, the new value equals the value at index 1, so it replaces that older candidate. At index 4, value one removes both larger back candidates. At index 6, it first removes the value three and then replaces the older equal minimum at index 4.
The emitted minimum values are . The corresponding latest witness indices are . Keeping equal values instead gives earliest indices for exactly the same sequence of minimum values.
Worked example 12.1.5
(A strictly decreasing input never needs expiry)
Take and . At the deque is . At the back value is removed, giving . At the back value is removed, giving , and the first answer is index 2 with value 3. At the front index 2 is not smaller than the left endpoint , so nothing expires; the back value is removed, giving and the answer index 3, value 2. At the same happens, giving and the answer index 4, value 1. Every removal was by dominance, the deque never held more than one index, and the output is .
Worked example 12.1.6
(The extreme widths one and n)
Take . With , each arrival first expires the front index and then appends , so the answers are : each element is its own window. With there is one window. At the deque is ; at the back value is removed, giving ; at the back value is false, so the deque is and the single answer is the front, index 1 with value 1.
Counterexample mode
Monotone values alone do not remove an expired front
Take and . After processing index 2, every candidate remains: indices have increasing values. At index 3 the new window is , so index 0 must be removed from the front. The correct answer is value two at index 1.
An implementation that only removes dominated back values would retain the old value one and return an observation outside the query. Index validity is a separate invariant from value monotonicity.
The explorer below replays each arrival, labels every removal as expiry or dominance, and compares the emitted witnesses with a direct scan under both tie policies.
A single expensive update can coexist with linear total work
Theorem 12.1.7
(Linear total work)
Over a whole run on a sequence of length with width , the deque performs operations and comparisons, so all window minima are computed in time with deque storage.
Proof X-ray
Charge each removal to the unique insertion of that index
Every index is appended exactly once. It can later be removed either from the front by expiry or from the back by domination, but never removed twice. Therefore the total number of successful removals across the entire run is at most .
The remaining loop checks contribute only constant work per arrival, and emitting an answer costs constant work. Thus all minima require total deque operations and comparisons. At most retained indices lie in one current window, giving deque storage.
This is an amortized claim, not a constant worst-case bound for one arrival. First insert the increasing values into a width- window. When zero arrives next, index 0 expires and the new zero removes the remaining candidates from the back. That one update takes work. Over the run, those removed candidates cannot be charged again.
The deque itself uses memory. A function that stores all answers additionally needs output space. The implementation below also materializes the input sequence for easy indexed access. An online implementation can instead store index:value pairs in the deque and emit answers as they occur, preserving working memory without retaining the whole input.
An implementation with explicit tie semantics
The function takes a nonempty finite input sequence and a valid integer width. The examples use integers, so comparisons are exact. The default returns the latest minimizing index; setting earliest=True changes only how equal back values are treated.
from collections import deque
def sliding_minima(values, width, earliest=False):
values = tuple(values)
if not 1 <= width <= len(values):
raise ValueError("width must lie between one and the sequence length")
candidates = deque()
answers = []
for right, value in enumerate(values):
left = right - width + 1
while candidates and candidates[0] < left:
candidates.popleft()
while candidates:
old_value = values[candidates[-1]]
dominated = old_value > value if earliest else old_value >= value
if not dominated:
break
candidates.pop()
candidates.append(right)
if left >= 0:
index = candidates[0]
answers.append((index, values[index]))
return answers
On the worked data, sliding_minima([4,2,2,5,1,3,1], 3) returns [(2,2),(2,2),(4,1),(4,1),(6,1)]. With earliest=True, it returns [(1,2),(1,2),(4,1),(4,1),(4,1)]. Width one returns each arrival itself. Width produces one answer for the entire input. The returned index is an original sequence index, not a position relative to the current window.
To compute maxima, reverse the domination comparison: discard a back value when it is no larger than the arriving value for a latest-maximum policy. Index expiry is unchanged. The proof uses the reversed value order, while the lifetime argument stays the same.
Know which deletions remain safe when queries change
Counterexample mode
A discarded index cannot be recovered when the left boundary moves backward
Use increasing values . After processing window , the deque contains all three indices. Move the left boundary to 1, giving window ; index 0 expires and is discarded. If the next query returns to , value one is needed again, but the deque no longer stores it.
Forward-moving left boundaries justify permanent expiry. Once backward movement is permitted, the same deletion rule no longer supports the queries. A static range-query structure or another method is needed for that different problem.
Fixed width is sufficient but not strictly necessary: the same lifetime reasoning can support windows whose left and right endpoints both move forward. What matters is that a dominated earlier value is never needed without its later replacement, and an expired value never becomes active again. Arbitrarily deleting a middle observation, revising an earlier value or processing arbitrary ranges changes those guarantees and requires a separate analysis.
Exercises and worked solutions
Quick check
(1. Track the index as well as the value)
For and width three, list the latest minimizing indices and the earliest minimizing indices. Why does the first full window have the same value under both policies but different returned indices?
Solution · Solution 1
Latest indices are and earliest indices are . The minimum values are in both cases. The first full window has equal minima at indices 1 and 2: removing equal back candidates retains 2, while keeping equal candidates leaves 1 at the front.
Quick check
(2. Complete the dominance argument)
Suppose and . A future width-k window has right endpoint and contains i. Write the inequalities that prove it also contains j. Why is a later expiry important?
Solution · Solution 2
Containment gives , so lies in the same window and supplies a value no larger than . Because is later, it cannot expire before under forward sliding. Thus the replacement cannot disappear while the older candidate is still needed.
Quick check
(3. Diagnose a missing expiry step)
An implementation processes at width three by removing only dominated back candidates. Which wrong answer does it return for the last window? Give the correct witness and the necessary index test.
Solution · Solution 3
It keeps index 0 at the front and wrongly returns value one. The last window is , whose correct witness is index 1 with value two. Remove front indices smaller than ; equivalently, remove indices at most .
Quick check
(4. Choose a duplicate policy rather than changing it accidentally)
Which back comparison produces the earliest minimum: greater than, or greater than or equal to? What monotonicity property do the retained values have in that version?
Solution · Solution 4
Use strictly greater than. Equal candidates remain in index order, so the earliest surviving equal minimum is at the front. Values are nondecreasing, with equality allowed. The greater-than-or-equal comparison makes them strictly increasing and implements the latest-witness policy instead.
Quick check
(5. Separate total work from the cost of one arrival)
Give a width-k input prefix and next value for which one insertion removes k minus one back candidates. Why does this not contradict a linear total bound?
Solution · Solution 5
Insert , then insert zero. The oldest candidate expires; zero removes all remaining back candidates, taking work for that arrival. Each of those indices was inserted once and can never be removed again, so the entire run still has only linearly many deque operations.
Quick check
(6. Identify the assumption broken by a returning window)
For , process , then , then ask for again. Which discarded index is needed again, and which forward-sliding assumption has failed?
Solution · Solution 6
Index 0 is removed when the left boundary advances to 1, but its value one is the minimum when the window returns to . Permanent expiry assumed the left boundary never moved backward. The new query violates that assumption, so this monotone deque state is insufficient for it.