Variable-size sliding window

Why it matters

Many questions ask for the best stretch of values that meets a rule. A runner wants the shortest run of days whose total distance is at least 20 kilometres. A phone plan wants the longest stretch of days where data use stays under a limit. A message filter wants the longest stretch of messages that use at most two languages. The length of the stretch is not known in advance, so the fixed-size window from the previous lesson does not fit.

The simple way to answer is to try every start and every end, and check each stretch. With 1000 values, that is about half a million stretches, and each one needs its own check. This lesson shows a faster way that looks at each value only a few times. The method is called a variable-size sliding window. The window grows when it is allowed to, and shrinks when the rule breaks.

The previous lesson covered the case where the window always has the same size k. Here the size changes at every step, so the program needs two positions instead of one. The arrays and vectors you need are covered in the earlier array lessons.

The idea: a caterpillar that stretches and bunches up

Picture a caterpillar on a branch. The front of the caterpillar is the right end of the window. The back is the left end. Its body is the stretch of values between them.

The caterpillar moves in one direction only. Its front moves forward to take in a new value. When the stretch breaks the rule, its back moves forward to let a value go. The front never goes back, and the back never goes back. Each value enters the window once and leaves it at most once. That is why the work stays small.

Here is the process written as steps. The values are 4, 1, 6, 2, 9, 3, 1 and 5. The rule is that the stretch sum must be at least 15. The brackets show the window after each step.

front at index 0: [4]               sum 4    rule not met, keep growing
front at index 1: [4 1]             sum 5    rule not met
front at index 2: [4 1 6]           sum 11   rule not met
front at index 3: [4 1 6 2]         sum 13   rule not met
front at index 4: [4 1 6 2 9]       sum 22   rule met, try to shrink
                  [1 6 2 9]         sum 18   still met, record length 4, shrink
                  [6 2 9]           sum 17   still met, record length 3, shrink
                  [2 9]             sum 11   rule broken, stop shrinking

At this point the best length is 3, the stretch 6, 2, 9. The front keeps moving, and the back keeps catching up when the rule is met. The rest of this lesson turns this process into code.

The pattern, before any example

Every program in this lesson has the same three parts. Learn the shape first, then fill in the details for each problem.

left = 0
for right from 0 to the last index:
    add values[right] to the window
    while the window breaks the rule:
        remove values[left] from the window
        left = left + 1
    record the length of the window if it is the best so far

The for loop moves the front. The while loop moves the back until the window is valid again. The recording step is where the difference between "longest" and "shortest" shows up.

For the longest valid stretch, the window must be valid when you record it. The shrink loop runs first, and the record comes after it.

For the shortest valid stretch, the window is valid inside the shrink loop. Each time the window is valid, you record its length, then remove the back value to see if a shorter valid stretch exists. The record happens inside the loop.

Worked example 1: the shortest run with a big enough sum

A runner logs the kilometres for each day. The question is: what is the shortest run of days whose total is at least 15 kilometres? The program below uses the shortest pattern.

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
// Returns the length of the shortest run of values whose sum is at least target.
// Returns 0 if no run qualifies. All values must be positive.
size_t shortest_run_at_least(const vector<long long>& values, long long target) {
    size_t best = values.size() + 1;
    long long sum = 0;
    size_t left = 0;
 
    for (size_t right = 0; right < values.size(); ++right) {
        sum += values[right];
        while (sum >= target) {
            size_t length = right - left + 1;
            if (length < best) {
                best = length;
            }
            sum -= values[left];
            ++left;
        }
    }
    return best == values.size() + 1 ? 0 : best;
}
 
int main() {
    vector<long long> steps = {4, 1, 6, 2, 9, 3, 1, 5};
    cout << "shortest run with sum >= 15: " << shortest_run_at_least(steps, 15) << "\n";
    cout << "shortest run with sum >= 100: " << shortest_run_at_least(steps, 100) << "\n";
}

Output:

shortest run with sum >= 15: 3
shortest run with sum >= 100: 0

The variable best starts at values.size() + 1. No real run can be that long, so the value means "nothing found yet". The function turns it into 0 at the end. Using 0 as the starting value would not work, because a shorter run would never beat it. The starting value must be bigger than any real answer.

The while loop is the key part. When the sum reaches 15 or more, the program records the length, removes the back value, and checks again. Here is the trace for the first large sum. At right equal to 4, the window is indexes 0 to 4, which is 4, 1, 6, 2 and 9. The sum is 22. The length 5 is recorded. The back value 4 is removed, leaving 18, and the length 4 is recorded. The back value 1 is removed, leaving 17, and the length 3 is recorded. The back value 6 is removed, leaving 11, which is below 15, so the loop stops. The best length so far is 3.

Each value is added once and removed at most once, so the total work is about twice the number of values. This is linear time, the same speed idea as the previous lesson.

Worked example 2: the longest stretch under a limit

A phone plan allows a total of 8 gigabytes of data over any stretch of days. The question is: what is the longest stretch of days that stays at or under 8? This uses the longest pattern. The record happens after the shrink loop.

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
// Returns the length of the longest run of values whose sum is at most limit.
// All values must be zero or positive.
size_t longest_run_at_most(const vector<long long>& values, long long limit) {
    size_t best = 0;
    long long sum = 0;
    size_t left = 0;
 
    for (size_t right = 0; right < values.size(); ++right) {
        sum += values[right];
        while (sum > limit) {
            sum -= values[left];
            ++left;
        }
        size_t length = right - left + 1;
        if (length > best) {
            best = length;
        }
    }
    return best;
}
 
int main() {
    vector<long long> usage = {3, 2, 6, 1, 4, 2, 2, 5};
    cout << "longest run with sum <= 8: " << longest_run_at_most(usage, 8) << "\n";
    cout << "longest run with sum <= 0: " << longest_run_at_most(usage, 0) << "\n";
}

Output:

longest run with sum <= 8: 3
longest run with sum <= 0: 0

Here the window is always valid after the while loop, so the length can be recorded safely. The longest valid run of length 3 is 1, 4, 2 or 4, 2, 2. Both sum to at most 8. No run of length 4 has a sum of 8 or less. The second call uses a limit of 0. No value is 0, so no run is valid, and the answer is 0.

The best variable starts at 0 here, because a valid run of length 0 is the empty case. That is the right starting value for a longest search, and it is the opposite of the shortest search above.

Worked example 3: at most two kinds

Now the rule is about variety, not a number. A market stall sells fruit in a row, and a shopper wants the longest run of fruit where at most two kinds appear. The window needs to know how many of each kind it holds. For that it uses a counting map. The map stores each value as a key and how many times it occurs in the window as the value. The unordered_map type is in the <unordered_map> header.

#include <cstddef>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
// Returns the length of the longest run that contains at most two different values.
size_t longest_run_two_kinds(const vector<int>& fruit) {
    unordered_map<int, int> counts;
    size_t best = 0;
    size_t left = 0;
 
    for (size_t right = 0; right < fruit.size(); ++right) {
        ++counts[fruit[right]];
        while (counts.size() > 2) {
            int leaving = fruit[left];
            if (--counts[leaving] == 0) {
                counts.erase(leaving);
            }
            ++left;
        }
        size_t length = right - left + 1;
        if (length > best) {
            best = length;
        }
    }
    return best;
}
 
int main() {
    vector<int> basket = {1, 2, 1, 2, 3, 2, 2, 4};
    cout << "longest run with two kinds: " << longest_run_two_kinds(basket) << "\n";
}

Output:

longest run with two kinds: 4

The rule is "the map has at most two keys". Every time the front adds a value, the count for that value goes up. If that makes three keys, the back moves forward and lowers the count of the value it leaves. When a count reaches 0, the key is removed from the map with erase. That removal matters. Without it, counts.size() would still count the value that has left the window, and the window would shrink too much.

Two runs of length 4 meet the rule: 1, 2, 1, 2 at the start, and 2, 3, 2, 2 in the middle. The answer is 4. The map's size is the number of kinds, so the rule check is a single comparison.

This example is harder than the first two because the state is not just a number. The map is the state. The same three-part pattern still applies. Only the add step and the remove step have become more work.

Common mistakes

The mistakes below are the ones that give wrong answers most often. Each sample was compiled with -std=c++20 -Wall, and the outputs are copied from the runs.

Using if where the rule needs while

A shrink loop must keep removing values until the rule is met again. An if removes at most one value per step, and that is not always enough. This sample is the shortest-run function with if in place of while:

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
size_t shortest_run_at_least(const vector<long long>& values, long long target) {
    size_t best = values.size() + 1;
    long long sum = 0;
    size_t left = 0;
    for (size_t right = 0; right < values.size(); ++right) {
        sum += values[right];
        if (sum >= target) {
            size_t length = right - left + 1;
            if (length < best) best = length;
            sum -= values[left];
            ++left;
        }
    }
    return best == values.size() + 1 ? 0 : best;
}
 
int main() {
    vector<long long> steps = {4, 1, 6, 2, 9, 3, 1, 5};
    cout << shortest_run_at_least(steps, 15) << "\n";
}

The output is:

5

The correct answer is 3, from the stretch 6, 2, 9. With if, the program removes only one value at right equal to 4, so the window stays too long for the rest of the run. The fix is the while in the worked example.

Using the window with negative values

The shrink step assumes that removing a value never makes the sum bigger. That is true when all values are zero or positive. With negative values, removing a value can increase the sum, so the back can move past a run that was valid. This sample has one negative value:

#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
size_t shortest_run_at_least(const vector<long long>& values, long long target) {
    size_t best = values.size() + 1;
    long long sum = 0;
    size_t left = 0;
    for (size_t right = 0; right < values.size(); ++right) {
        sum += values[right];
        while (sum >= target) {
            size_t length = right - left + 1;
            if (length < best) best = length;
            sum -= values[left];
            ++left;
        }
    }
    return best == values.size() + 1 ? 0 : best;
}
 
int main() {
    vector<long long> v = {1, -1, 5};
    cout << "shortest with negatives: " << shortest_run_at_least(v, 5) << "\n";
}

The output is:

shortest with negatives: 3

The correct answer is 1, because the single value 5 is already at least 5. The program records the run 1, -1, 5 at length 3. Then the back removes the 1, and the sum falls to 4, which is below the target. The loop stops, so the back never moves past the -1 to reach the 5 by itself. Removing a negative value would raise the sum, and the loop does not account for that. For data with negative values, another method is needed, and that method is not covered here.

Recording the length at the wrong point

For the longest search, recording inside the shrink loop counts a window that still breaks the rule, so the answer can be too big. For the shortest search, recording after the shrink loop counts a window that no longer meets the rule, so the answer can be too small. Check which pattern the question needs before you write the record step.

Using 0 as the starting value for the shortest search

If best starts at 0 for a shortest search, no length can be smaller, so best stays 0 for every input. The starting value must be bigger than any real answer. The worked example uses values.size() + 1 for this reason, and then turns that marker into 0 at the end, which means "no run".

Practice

Exercise 1

Trace the shortest-run function on the values 4, 1, 6, 2, 9, 3, 1, 5 with target 15. Write down the window after each change of right. Give the length recorded each time.

Show the answer

With right equal to 4, the window is 4, 1, 6, 2, 9 with sum 22. The records are 5, then 4 after removing 4, then 3 after removing 1. The back then removes 6 and the sum becomes 11. At right equal to 5, the sum is 14. At right equal to 6, the sum is 15, the window is 2, 9, 3, 1, which has length 4, and the back removes 2 to leave 13. At right equal to 7, the sum is 18, the window is 9, 3, 1, 5 with length 4, and the back removes 9 to leave 9. The final answer is 3.

Exercise 2

Write a function that returns the length of the longest run of values where no value appears twice. Use a set that stores the values inside the window.

Show the answer

size_t longest_distinct_run(const vector<int>& values) {
    unordered_set<int> inside;
    size_t best = 0;
    size_t left = 0;
 
    for (size_t right = 0; right < values.size(); ++right) {
        while (inside.contains(values[right])) {
            inside.erase(values[left]);
            ++left;
        }
        inside.insert(values[right]);
        size_t length = right - left + 1;
        if (length > best) {
            best = length;
        }
    }
    return best;
}

The unordered_set type is in the <unordered_set> header. The shrink loop moves the back until the new value is no longer inside the window. With the values 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, the function returns 6, for the run 4, 1, 5, 9, 2, 6. With the values 7, 7, 7, it returns 1.

Exercise 3

The shortest-run function returns only the length. Change the shortest-run function so it also returns the index where the shortest valid run starts. Explain which index you would store, and why.

Show the answer

Store the value of left at the moment the length is recorded. The window runs from left to right, so left is the start. Keep the start in a second variable next to best, and update both when a shorter run is found. For the values 4, 1, 6, 2, 9, 3, 1, 5 and target 15, the shortest run is 6, 2, 9, which starts at index 2.

Exercise 4

Explain why the longest-run function records the length after the shrink loop, and the shortest-run function records it inside the loop.

Show the answer

The longest search needs a window that already meets the rule. The shrink loop makes it meet the rule, so the record happens after. The shortest search wants to find the smallest window that meets the rule. Each time the window meets the rule, the program records it and then shrinks to test a smaller one. The record must happen inside the loop, because the loop is where the window is still valid.

Summary

• A variable-size sliding window has a front that moves right to add values and a back that moves right to remove them.
• Each value is added once and removed at most once, so the work is linear in the number of values.
• For the longest valid stretch, shrink until the window is valid, then record its length.
• For the shortest valid stretch, record the length inside the shrink loop, then keep shrinking to test a smaller window.
• Use while for the shrink step, not if, because one removal is often not enough to restore the rule.
• In a sum problem the method needs zero or positive values. Removing a value then never raises the sum, so the shrink loop can stop safely.