Why it matters
Many questions ask about a stretch of values rather than the whole list. A shop wants the total sales for every run of 7 days. A heart monitor wants the average heart rate over the last 30 seconds. A spam filter wants the number of messages in the last minute. Each of these asks about a block of neighbouring values that has a fixed length.
The simple way to answer is to add up each block from scratch. That works, but it repeats a lot of work. Two blocks that overlap share most of their values, and the simple way adds those shared values again every time. This lesson shows the faster way. You keep a running total, and each step changes it by only two values.
The technique is called a fixed-size sliding window. The window is a block of k values that moves one place to the right at a time. "Fixed-size" means k does not change while the window moves. The next lesson covers the case where the size changes. The array basics you need are in the lessons on arrays and vectors, and the sums here are plain integer addition.
The idea: a frame that slides along a row of boxes
Picture a row of boxes on a table. Each box holds one number. Now place a cardboard frame over exactly three boxes. You can see the numbers inside the frame and nothing else. Add up the three numbers. That is the first answer.
Slide the frame one box to the right. Two boxes stay inside the frame. One box leaves the frame on the left, and one new box enters on the right. To get the new total, you do not need to add three numbers again. You can take the old total, subtract the box that left, and add the box that entered. Two changes, and you have the new answer.
Here is the same idea written as text. The brackets show the window. The numbers are the daily sales from the first example.
values: 3 1 4 1 5 9 2 6
window 1: [3 1 4] 1 5 9 2 6 sum 8
window 2: 3 [1 4 1] 5 9 2 6 sum 8 - 3 + 1 = 6
window 3: 3 1 [4 1 5] 9 2 6 sum 6 - 1 + 5 = 10Each new sum comes from the old sum. Subtract the value that left on the left, and add the value that entered on the right. The arithmetic in the brackets is the whole technique.
Worked example 1: the sum of every 3 days
Suppose a shop records its sales for 8 days. The task is to print the total for every block of 3 days in a row. The program below does this in one pass after the first block.
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> sales = {3, 1, 4, 1, 5, 9, 2, 6};
size_t k = 3;
int sum = 0;
for (size_t i = 0; i < k; ++i) {
sum += sales[i];
}
cout << "days 0-2: sum " << sum << "\n";
for (size_t right = k; right < sales.size(); ++right) {
sum += sales[right];
sum -= sales[right - k];
cout << "days " << right - k + 1 << "-" << right << ": sum " << sum << "\n";
}
}Compile and run it with the flags used in this course:
g++ -std=c++20 -Wall -o sales sales.cpp
./salesThe output is:
days 0-2: sum 8
days 1-3: sum 6
days 2-4: sum 10
days 3-5: sum 15
days 4-6: sum 16
days 5-7: sum 17The program has two parts. The first loop adds up the first window, the values at indexes 0, 1 and 2. This is the only place where the program adds k values. The second loop starts at index k, which is the first value that is not yet in the window. The window always ends at right, so it starts at right - k + 1.
Inside the second loop there are two lines. sum += sales[right]; adds the new value on the right. sum -= sales[right - k]; removes the value that just left on the left. The value that left is k places behind the new one. With right equal to 3 and k equal to 3, the value that left is at index 0.
Check the first change by hand. The sum for days 0 to 2 was 8. The new value at index 3 is 1, and the value that left is at index 0, which is 3. So the new sum is 8 + 1 - 3, which is 6. The output agrees.
The reason this is faster
Count the additions. A program that adds each window from scratch adds k values for every window. With 8 values and k equal to 3, there are 6 windows, so it does 6 times 3, which is 18 additions. The sliding version does 3 additions for the first window. After that it does 2 changes for each of the 5 remaining windows, which is 10 more. The total is 13.
The gap grows with the size of the data. If there are one million values and k is 1000, the simple way does about one thousand additions per window, and the sliding way does two changes per window. The sliding version does the same amount of work per step no matter how big k is. Computer scientists call this linear time, which means the work grows in step with the number of values. The simple way is slower, because its work grows with the number of values times k.
Worked example 2: the best window
Often the question is not "print every sum" but "which window has the largest sum?" A temperature log might ask for the warmest block of 3 readings. The same loop works. Keep a second variable that remembers the best sum seen so far.
#include <cstddef>
#include <iostream>
#include <optional>
#include <vector>
using namespace std;
// Returns the largest sum of any k values in a row, or nothing if k is too big.
optional<long long> best_window_sum(const vector<int>& values, size_t k) {
if (k == 0 || k > values.size()) {
return nullopt;
}
long long sum = 0;
for (size_t i = 0; i < k; ++i) {
sum += values[i];
}
long long best = sum;
for (size_t right = k; right < values.size(); ++right) {
sum += values[right];
sum -= values[right - k];
if (sum > best) {
best = sum;
}
}
return best;
}
// The slow way: add up every window from scratch. Used only to check the fast one.
long long best_window_sum_slow(const vector<int>& values, size_t k) {
long long best = 0;
bool first = true;
for (size_t start = 0; start + k <= values.size(); ++start) {
long long sum = 0;
for (size_t i = start; i < start + k; ++i) {
sum += values[i];
}
if (first || sum > best) {
best = sum;
first = false;
}
}
return best;
}
int main() {
vector<int> temps = {-2, 5, 3, -1, 4, 4, -3, 2};
for (size_t k : {1, 2, 3, 8, 9, 0}) {
auto result = best_window_sum(temps, k);
if (result) {
cout << "k=" << k << " best=" << *result
<< " slow=" << best_window_sum_slow(temps, k) << "\n";
} else {
cout << "k=" << k << " no valid window\n";
}
}
}Output:
k=1 best=5 slow=5
k=2 best=8 slow=8
k=3 best=7 slow=7
k=8 best=12 slow=12
k=9 no valid window
k=0 no valid windowThree details in this program matter for real code.
The first is the check at the top. If k is 0, a window has no values and the question has no meaning. If k is bigger than the number of values, no full window fits. The function returns std::nullopt, which means "no answer". The optional type is in the <optional> header. It lets the caller tell "no answer" apart from a real answer of 0. A plain int return value cannot do that without a special number.
The second is the type of the sum. The values are int, but a sum of many large values can pass the largest int. The program keeps the sum in a long long, which is a whole-number type that holds much bigger values. Choose the type for the total, not for each value.
The third is the best_window_sum_slow function. It adds every window from scratch. It is too slow for big inputs, so the course uses it only to confirm the fast version on small data. Testing a fast method against a simple slow method is a common habit in real code. The two must agree on every input you try.
Walk through the k equal to 3 case by hand. The first window is 5, 3 and -1, which adds to 7. The next window is 3, -1 and 4, which adds to 6. The window after that is -1, 4 and 4, which adds to 7. The fast version updates the sum each time and keeps 7 as the best so far. The output says 7, which matches.
Worked example 3: counting windows that pass a test
The window does not have to produce a number to be useful. Often you only count how many windows pass a test. The next function counts the windows whose sum is even. It keeps the same running sum, and it adds one to a counter when the test passes.
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
// Counts windows of k values whose sum is even.
size_t count_even_windows(const vector<int>& values, size_t k) {
if (k == 0 || k > values.size()) {
return 0;
}
long long sum = 0;
for (size_t i = 0; i < k; ++i) {
sum += values[i];
}
size_t count = (sum % 2 == 0) ? 1 : 0;
for (size_t right = k; right < values.size(); ++right) {
sum += values[right];
sum -= values[right - k];
if (sum % 2 == 0) {
++count;
}
}
return count;
}
int main() {
vector<int> v = {2, 7, 1, 8, 2, 8, 1, 8};
cout << "even windows of 3: " << count_even_windows(v, 3) << "\n";
}Output:
even windows of 3: 3The six windows of 3 values have sums 10, 16, 11, 18, 11 and 17. Three of them are even: 10, 16 and 18. The count is 3, which matches the output.
Notice the first window is handled before the loop. The first window does not come from a change, so its test must be done separately. A common bug is to test only the windows produced inside the loop. That bug misses the first window and gives an answer that is one too small.
Common mistakes
The mistakes below are the ones that appear most often when students write this technique for the first time. Each one has a real message or a clear wrong result.
Using a signed index against the size
The loop variable and the size of the vector have different types. The size is an unsigned number. This program starts right at k but declares it as an int:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> sales = {3, 1, 4, 1, 5, 9, 2, 6};
int k = 3;
int sum = 0;
for (int i = 0; i < k; ++i) {
sum += sales[i];
}
for (int right = k; right < sales.size(); ++right) {
sum += sales[right] - sales[right - k];
cout << sum << "\n";
}
}Compiling it with -Wall gives this warning:
bad1.cpp: In function ‘int main()’:
bad1.cpp:12:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
12 | for (int right = k; right < sales.size(); ++right) {
| ~~~~~~^~~~~~~~~~~~~~The program still runs in this case, but the warning is a sign of a real risk. The fix is to declare right and k as size_t, as the worked examples do.
Subtracting from an unsigned index that is too small
This is the most dangerous mistake. The loop below starts at 0 instead of k, so right - k is negative on the first step. A size_t cannot hold a negative number. The subtraction wraps around to a very large number instead.
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> sales = {3, 1, 4, 1, 5, 9, 2, 6};
size_t k = 3;
int sum = 0;
for (size_t right = 0; right < sales.size(); ++right) {
sum += sales[right];
sum -= sales[right - k];
cout << sum << "\n";
}
}With right equal to 0, the expression right - k is 0 minus 3, which becomes 18446744073709551613 in a 64-bit size_t. The [] operator then reads far outside the vector. On the Ubuntu g++ 15.2 used to check this lesson, the run stops at once with an assertion message:
/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.The exit code is 134, which means the program stopped itself. Other builds may not check the index at all, and the program then reads memory it does not own. The rule is simple: only subtract k from right when right is at least k. The loop in the worked examples starts at k for this reason.
Using at() and getting an exception
The at() function checks the index and throws an error when it is out of range. A program that does not catch the error stops with a message. This sample reads one value too far:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> sales = {3, 1, 4};
size_t k = 5;
int sum = 0;
for (size_t i = 0; i < k; ++i) {
sum += sales.at(i);
}
cout << sum << "\n";
}The output is:
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 3) >= this->size() (which is 3)The message tells you what went wrong. The index was 3, and the vector has size 3, so the last valid index is 2. The mistake is k being larger than the vector. A check such as if (k > values.size()) at the top of the function prevents the problem.
Forgetting to remove the value that left
If the program adds the new value but never subtracts the old one, no error appears. The sums just grow and become wrong. This program forgets the removal:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> bad = {3, 1, 4, 1, 5};
int wrong = 0;
for (size_t i = 0; i < 2; ++i) wrong += bad[i];
for (size_t right = 2; right < bad.size(); ++right) {
wrong += bad[right];
cout << "wrong: " << wrong << "\n";
}
}The output is:
wrong: 8
wrong: 9
wrong: 14This sample sums windows of 2 values. The correct sums for the windows that end at index 2, 3 and 4 are 5, 5 and 6. Each wrong line adds the new value to the running total but never takes the old value away, so the totals keep growing. When the sums keep growing, check that the removal line is there.
Forgetting the first window
The loop that slides starts at k, so the first window must be summed before it. If the first sum is left at 0, every later answer is off by the sum of the values that should have been in the first window. Always write the first window as its own step, and check it by hand on a small input.
Practice
Exercise 1
Given the values 2, 7, 1, 8, 2, 8, 1, 8, write the sum of every window of 3 values. Do it by hand first, then check against the program in this lesson.
Show the answer
The sums are 10, 16, 11, 18, 11 and 17. The windows are 2 7 1, 7 1 8, 1 8 2, 8 2 8, 2 8 1 and 8 1 8. The program prints the first sum as the start value, then each later sum in turn.
Exercise 2
Write a function first_window_at_least that takes the values, k and a target sum. It returns the index where the first window whose sum is at least the target begins. It returns -1 if no window qualifies. Use the sliding method, so the work is linear.
Show the answer
long long first_window_at_least(const vector<int>& values, size_t k, long long target) {
if (k == 0 || k > values.size()) {
return -1;
}
long long sum = 0;
for (size_t i = 0; i < k; ++i) {
sum += values[i];
}
if (sum >= target) {
return 0;
}
for (size_t right = k; right < values.size(); ++right) {
sum += values[right];
sum -= values[right - k];
if (sum >= target) {
return static_cast<long long>(right - k + 1);
}
}
return -1;
}With the values 2, 7, 1, 8, 2, 8, 1, 8, k equal to 3 and target 15, the function returns 1. The window that starts at index 1 is 7, 1 and 8, which adds to 16. The window that starts at index 0 adds to 10, which is too small. With target 100 the function returns -1.
Exercise 3
Write a function count_even_windows that counts the windows of k values whose sum is even. Test it on the values from Exercise 1 with k equal to 3. The answer should be 3.
Show the answer
The function is in the worked example 3 section of this lesson. It adds the first window, tests it, and then slides the window once for each later position. Each window is tested once. For the values from Exercise 1, the even sums are 10, 16 and 18, so the count is 3.
Exercise 4
Explain why the sliding loop starts at index k and not at index 0.
Show the answer
At index k, the window has just become full, and right - k is 0, which is the first value to remove. Starting at index 0 would make right - k negative. With size_t, that negative number wraps to a huge index, and the program reads outside the vector.
Summary
- A fixed-size sliding window is a block of
kvalues that moves one place to the right at a time. - Sum the first window once. After that, add the value that enters on the right and subtract the value that leaves on the left.
- The method does about two changes per window, so the work grows with the number of values, not with the number of values times
k. - Start the sliding loop at index
k, soright - kis never negative when the index type issize_t. - Check the size of
kfirst. Ifkis 0 or bigger than the number of values, return "no answer" instead of reading outside the vector. - Test the fast method against a simple slow method on small inputs, and make sure the two always agree.