Why this matters
A sensor in a factory records a temperature once per second. A safety screen needs, for every 60-second block of readings, the hottest value in that block. The blocks overlap. The first block covers seconds 1 to 60, the next covers seconds 2 to 61, and so on. A plain loop that scans each block from start to end does about 60 checks per block. A day has 86,400 seconds, so there are about 86,400 blocks, and the plain loop makes about 5 million checks. The cost grows with the size of each block.
This lesson shows a technique that answers the same question in one pass. Each reading is handled a fixed number of times, no matter how big the block is. It uses a deque, which is a container that lets you add and remove values at both ends quickly. The word "monotonic" means moving in one direction only. Here, the values kept in the deque always go in one direction: from the front to the back, they only go down.
The same pattern appears in interview questions, in software that tracks the highest price over a recent period, and in signal processing. This lesson keeps the largest value. The smallest value works the same way with the comparison reversed, and one exercise at the end shows that change.
Words you need first
A sliding window is a block of k items that sits on a list and moves one step to the right at a time. With k equal to 3 and the list 1 3 -1 -3 5, the windows are 1 3 -1, then 3 -1 -3, then -1 -3 5. Each step drops the oldest item of the window and takes in one new item.
A deque (say "deck") is a double-ended queue. You can add and remove values at the front and at the back, and each of those four moves takes constant time. In C++ it is std::deque, from the header <deque>.
Constant time means the cost of one operation does not grow with the size of the container. It is written O(1). A loop that does one constant-time step per item, for n items, costs O(n) in total. The letter n stands for the number of items.
An index is the position of an item in a list. Counting starts at 0, so the first item has index 0, the second has index 1, and so on. In C++ you read the value at an index with nums[i].
Amortized cost is the average cost per step over a whole run. Some steps in this lesson do a lot of removing, but each value is added once and removed at most once. Spread over all the steps, the average stays constant.
The slow way first
Start with the simplest correct program. For each window, scan all k items and keep the biggest.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums{1, 3, -1, -3, 5, 3, 6, 7};
std::size_t k = 3;
for (std::size_t start = 0; start + k <= nums.size(); ++start) {
int best = nums[start];
for (std::size_t i = start; i < start + k; ++i) {
best = std::max(best, nums[i]);
}
std::cout << best << ' ';
}
std::cout << '\n';
}Save the file as naive.cpp, then build and run it with the course flags:
g++ -std=c++20 -Wall -o naive naive.cpp
./naive
3 3 5 5 6 7 Check the first two numbers by hand. The first window is 1 3 -1, and its biggest value is 3. The second window is 3 -1 -3, which also has biggest value 3. The third window is -1 -3 5, with biggest value 5. The output has six numbers because there are six windows: the list has eight items and each window has three.
The outer loop runs once for each window, which is about n times. The inner loop reads k items for each window. The total is about n times k reads. For a list of 1,000,000 numbers and a window of 1,000 numbers, that is about one billion reads. The program is correct, but it is slow when the list is large or the window is wide.
Two details in the code matter later. nums.size() returns an unsigned type, which is the same type as std::size_t on common systems, so the loop counters use that type too. The condition start + k <= nums.size() stops the loop when the window would run past the end of the list.
The idea: throw away what cannot win
Look at two windows that follow each other: 3 -1 -3 and -1 -3 5. The value -3 at index 3 sits in both of them, and so does -1. Now compare index 3 with index 4, which holds the value 5. Index 4 arrives after index 3, and it is bigger. Anything that stays in the window as long as index 3 does, and is smaller than index 4, can never be the biggest value of a window. Index 3 belongs to that group, because index 4 is bigger and lasts at least as long. So index 3 can be dropped.
This is the key rule. When a new value arrives, every older value at the back of the deque that is less than or equal to the new value can be removed. Those older values lose on size, and they also leave the window earlier than the new value does, so they can never win later.
After that clean-up, the deque holds only the values that might still be the biggest in some window. Each value in the deque is bigger than every value after it. Read from the front to the back, the values go down. The front is the largest value in the current window.
Each step has three parts.
- If the front index has slid out of the window, remove it from the front.
- Remove indices from the back while their values are less than or equal to the new value.
- Add the new index at the back.
After those three parts, once the first full window exists, the front of the deque holds the index of the window's largest value.
The deque stores indices, not the values themselves. This matters for part 1. The program needs to know when the front value has left the window, and a value by itself does not say where it sits in the list. An index does. Checking whether an index is still in the window takes one addition and one comparison.
Worked example 1: the deque at work
Here is the complete function. It returns the largest value of every window of size k. Read it line by line, and compare each line with the three parts above.
#include <cstddef>
#include <deque>
#include <iostream>
#include <vector>
std::vector<int> window_max(const std::vector<int>& nums, std::size_t k) {
std::vector<int> result;
if (k == 0) {
return result;
}
std::deque<std::size_t> dq; // indices; their values go down from front to back
for (std::size_t i = 0; i < nums.size(); ++i) {
if (!dq.empty() && dq.front() + k <= i) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i + 1 >= k) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
int main() {
std::vector<int> nums{1, 3, -1, -3, 5, 3, 6, 7};
for (int m : window_max(nums, 3)) {
std::cout << m << ' ';
}
std::cout << '\n';
}Output:
3 3 5 5 6 7 The window that ends at index i covers the indices from i - k + 1 up to i. A front index is outside that window when it is smaller than i - k + 1, which is the same as saying front + k <= i. The code writes the check that way on purpose. Subtracting from i can go below zero when i is small, and with unsigned numbers a value below zero does not become negative. It wraps around to a very large number, so the comparison would give a wrong answer. Adding k to the front index avoids the problem.
The while loop is the clean-up from the previous section. It removes the back indices whose values do not beat the new value.
The line if (i + 1 >= k) records an answer only once the first full window exists. Before that, the window has fewer than k values, so there is no answer to record.
To see the deque change, print it after each step. The next program uses the same three parts, plus one print line.
#include <cstddef>
#include <deque>
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums{1, 3, -1, -3, 5, 3, 6, 7};
std::size_t k = 3;
std::deque<std::size_t> dq;
for (std::size_t i = 0; i < nums.size(); ++i) {
if (!dq.empty() && dq.front() + k <= i) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
std::cout << "i=" << i << " adds " << nums[i] << " | deque:";
for (std::size_t idx : dq) {
std::cout << ' ' << idx << '(' << nums[idx] << ')';
}
std::cout << '\n';
}
}Output:
i=0 adds 1 | deque: 0(1)
i=1 adds 3 | deque: 1(3)
i=2 adds -1 | deque: 1(3) 2(-1)
i=3 adds -3 | deque: 1(3) 2(-1) 3(-3)
i=4 adds 5 | deque: 4(5)
i=5 adds 3 | deque: 4(5) 5(3)
i=6 adds 6 | deque: 6(6)
i=7 adds 7 | deque: 7(7)Each line shows the deque after its three parts have run. Each entry is index(value). The values go down from left to right in every line, and the leftmost entry is the answer for that window once the window is full.
Take the line i=4 adds 5 in detail. Before this step the deque held 1(3) 2(-1) 3(-3). First, part 1 runs. The front index is 1, and 1 + 3 <= 4 is true, so index 1 leaves the window and is removed. The deque is now 2(-1) 3(-3). Part 2 runs next. The back value is -3, which is at most 5, so index 3 goes. Then the back value -1 is at most 5, so index 2 goes too. The deque is empty. Part 3 adds index 4. The deque is 4(5), and the answer for the window -1 -3 5 is 5.
Now take i=6 adds 6. Before this step the deque held 4(5) 5(3). Part 1 does nothing, because 4 + 3 <= 6 is false, so index 4 is still inside the window that covers indices 4, 5 and 6. Part 2 removes index 5, because 3 is at most 6, and then index 4, because 5 is at most 6. Part 3 adds index 6. The answer for that window is 6, which matches the output.
The printed deque is a good check on your own traces. If you trace a list by hand and your deque differs from the printed one after some step, look for the first step where they differ. That step tells you which rule you applied wrongly.
Worked example 2 checks the function against the slow version on random inputs. Random tests find corner cases that a few hand-picked lists miss, such as equal values, windows of size 1, and windows as large as the whole list.
#include <algorithm>
#include <cstddef>
#include <deque>
#include <iostream>
#include <random>
#include <vector>
std::vector<int> naive_max(const std::vector<int>& nums, std::size_t k) {
std::vector<int> result;
for (std::size_t start = 0; start + k <= nums.size(); ++start) {
result.push_back(*std::max_element(nums.begin() + start, nums.begin() + start + k));
}
return result;
}
std::vector<int> window_max(const std::vector<int>& nums, std::size_t k) {
std::vector<int> result;
if (k == 0) {
return result;
}
std::deque<std::size_t> dq;
for (std::size_t i = 0; i < nums.size(); ++i) {
if (!dq.empty() && dq.front() + k <= i) {
dq.pop_front();
}
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i + 1 >= k) {
result.push_back(nums[dq.front()]);
}
}
return result;
}
int main() {
std::mt19937 gen(2026); // a fixed seed, so every run tests the same lists
int cases = 0;
int mismatches = 0;
for (int t = 0; t < 2000; ++t) {
std::size_t n = gen() % 30 + 1;
std::vector<int> nums(n);
for (int& x : nums) {
x = static_cast<int>(gen() % 101) - 50;
}
std::size_t k = gen() % n + 1;
++cases;
if (naive_max(nums, k) != window_max(nums, k)) {
++mismatches;
}
}
std::cout << "cases checked: " << cases << ", mismatches: " << mismatches << '\n';
}Output:
cases checked: 2000, mismatches: 0The generator std::mt19937 is a standard random number source from <random>. The fixed seed 2026 makes the lists the same on every run. Each list has between 1 and 30 numbers, with values from -50 to 50, and the window size is between 1 and the length of the list. Zero mismatches means the two functions gave the same answer on all 2000 lists. That is evidence, not proof. Random tests can miss a case that they do not happen to generate, but they catch most mistakes made while writing a clever function.
The cost of the fast version is O(n) in total. Each index goes into the deque once and leaves it at most once. The while loop looks as if it could do a lot of work in one step, but the total number of removals across the whole run can never be more than the total number of additions. Spread over all the steps, that is a constant cost per value.
Common mistakes
Storing values instead of indices. A beginner often writes std::deque<int> and pushes the values. The code then has no way to tell whether the front value is still in the window. If two windows contain the same number, the program cannot tell which copy is which. Store indices, and read the values through nums[index].
Reading the front before removing the old index. The answer must come after part 1. If part 1 is skipped, the deque can keep an index from a window that has already passed, and the answer is wrong. The program below leaves out part 1 on purpose.
#include <cstddef>
#include <deque>
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums{9, 1, 1};
std::size_t k = 2;
std::deque<std::size_t> dq;
for (std::size_t i = 0; i < nums.size(); ++i) {
// Mistake: the front index is never removed when it leaves the window.
while (!dq.empty() && nums[dq.back()] <= nums[i]) {
dq.pop_back();
}
dq.push_back(i);
if (i + 1 >= k) {
std::cout << nums[dq.front()] << ' ';
}
}
std::cout << '\n';
}Output:
9 9 The correct answer is 9 1. The windows are 9 1, whose largest value is 9, and 1 1, whose largest value is 1. The second answer is wrong because the 9 at index 0 is still at the front, even though index 0 is no longer in the second window.
Calling front() on an empty deque. When every index has been removed and nothing is left, dq.front() has no value to return. The C++ standard says this is undefined behaviour, which means the program may do anything. On the Ubuntu g++ 15.2 build used to check this lesson, the program stops with a message. This program reads the front of an empty deque:
#include <deque>
#include <iostream>
int main() {
std::deque<int> dq;
std::cout << dq.front() << '\n';
}Built and run on that same build, it prints this message and exits:
/usr/include/c++/15/bits/stl_deque.h:1513: std::deque<_Tp, _Alloc>::reference std::deque<_Tp, _Alloc>::front() [with _Tp = int; _Alloc = std::allocator<int>; reference = int&]: Assertion '!this->empty()' failed.The message names the call, front(), and the rule that failed, !this->empty(). In the window program, the deque is never empty when it is read, because part 3 always adds the new index before the answer is read. If you change the order of the parts, you may see this message.
Using a signed counter to compare with a size. The function size() returns an unsigned type. Writing int i and then i < nums.size() compares a signed number with an unsigned one, and g++ warns about it. This program has that line:
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums{4, 9, 2};
for (int i = 0; i < nums.size(); ++i) {
std::cout << nums[i] << '\n';
}
}Compiled with g++ -std=c++20 -Wall, the build prints this warning. It still builds, and this small program runs correctly, but the warning marks a bug waiting to happen.
warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]The fix is to use std::size_t i, as the lesson's code does.
Reading the back instead of the front. The back of the deque holds the newest index that survived the clean-up. Its value is the smallest of the candidates, not the largest. The answer for a window is always the front.
Practice
Exercise 1. Work out the window maximum by hand for the list 4 2 12 3 8 1 7 with k equal to 3. Write the five windows and their largest values.
Show the answer
The windows are 4 2 12, 2 12 3, 12 3 8, 3 8 1 and 8 1 7. Their largest values are 12, 12, 12, 8 and 8. The output is 12 12 12 8 8.
Exercise 2. For the list 2 2 1 with k equal to 2, which indices are in the deque after index 2 is processed? Use the three parts, and remember the rule that removes back values less than or equal to the new value.
Show the answer
The deque holds indices 1 and 2. Index 0 is removed when index 1 arrives, because the value 2 at index 0 is less than or equal to the new value 2. Index 1 is then at the back. At index 2, the value 1 is not at least the back value 2, so index 2 is added after index 1. The deque is 1(2) 2(1).
Exercise 3. Change the function so that it returns the smallest value of each window. Give the change in one line and test it on the list 4 2 12 3 8 1 7 with k equal to 3, then on the list 2 2 1 with k equal to 2.
Show the answer
Change the <= in the while loop to >=. The deque then keeps values that go up from front to back, and the front is the smallest value. For the first list the output is 2 2 3 1 1, and for the second list the output is 2 1. Both outputs match the hand-worked windows.
Exercise 4. Explain why the code writes dq.front() + k <= i and not i - k >= dq.front(). Use the unsigned type std::size_t in your explanation.
Show the answer
Both lines mean the same thing when i is at least k. The second form subtracts k from i. When i is smaller than k, that subtraction goes below zero. With an unsigned type, the result wraps around to a very large number, so the check is wrong during the first few steps. The first form adds to the front index, so no subtraction can wrap.
Exercise 5. A list has 8 numbers. Count the most deque pushes and pops the function can make while it runs, and say what that means for the cost.
Show the answer
Each of the 8 indices is pushed once, which is 8 pushes. Each index is removed at most once, from the front or the back, which is at most 8 pops. The total is at most 16 deque changes. The count grows in step with the list length, so the cost is O(n).
Summary
- A sliding window is a block of
kvalues that moves one step at a time along a list. - A monotonic deque keeps the indices of the values that could still be a window's largest, with the values going down from front to back.
- The front of the deque is the answer for the current window, once the first full window exists.
- Each step removes the front index when it leaves the window, then removes back values that cannot win, then adds the new index.
- Storing indices, not values, is what lets the program tell when the front has left the window.
- Each index enters and leaves the deque at most once, so the whole run costs O(n), while the simple method costs about n times
k.