Skip to content
wannacode

Sliding window

In short: A sliding window computes something for every consecutive range by adding the new element and removing the old one at each step: O(n) instead of O(n · k).

Problem

The revenue for the last 365 days

The shop's dashboard shows, for every day, the revenue for the last 365 days. The history is 10 years: 3650 days. The code computes every window from scratch: for each day it adds up the 365 days before it.

static long adds = 0;


static int[] Recompute(int[] sales, int k)
{
    int[] sums = new int[sales.Length - k + 1];
    for (int start = 0; start + k <= sales.Length; start++)
    {
        int sum = 0;
        for (int d = start; d < start + k; d++)
        {
            adds++;
            sum += sales[d];
        }
        sums[start] = sum;
    }
    return sums;
}
int[] sales = new int[3650];
for (int d = 0; d < sales.Length; d++)
{
    sales[d] = (d * 37) % 101 * 10 + 500;
}
int[] sums = Recompute(sales, 365);
Console.WriteLine("Windows: " + sums.Length);
Console.WriteLine("Additions: " + adds);
Console.WriteLine($"The best 365 days: €{sums.Max()}");
Output
Windows: 3286
Additions: 1199390
The best 365 days: €366050

3286 windows of 365 additions each: 1,199,390. That is n·k: with 1000 products, one chart each, it becomes 1.2 billion additions every night.

Yet two neighbouring windows differ in just two days. The other 364 are added up again and again.

The idea

Slide the window: +new day, −old day

The sum for days 2–8 is the sum for days 1–7, plus day 8, minus day 1. Day 8 comes into the window, day 1 goes out. The days in between are not touched.

So:

  • the first window is added up once: k additions;
  • every next one is the previous one + the new day − the oldest day: two operations, however large the window.

This is called a sliding window: a window of fixed length that moves by one element, while its result is updated from the previous one. Instead of (n − k + 1) · k operations there are k + 2(n − k). That is O(n), not O(n·k).

The window is two pointers moving in the same direction, as in the previous lesson: its start and its end. Here the distance between them is always k.

See it

The week slides

The sales for 12 days and the sum for every 7 consecutive days. The average for the week is the sum divided by 7.

static int[] Slide(int[] sales, int k)
{
    int[] sums = new int[sales.Length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++)
    {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.Length; i++)
    {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}
int[] sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];
int[] sums = Slide(sales, 7);
for (int d = 0; d < sums.Length; d++)
{
    Console.WriteLine($"Days {d + 1}–{d + 7}: €{sums[d]}");
}
Output
Days 1–7: €5430
Days 2–8: €5500
Days 3–9: €5470
Days 4–10: €5540
Days 5–11: €5560
Days 6–12: €5830

static int[] Slide(int[] sales, int k)
{
    int[] sums = new int[sales.Length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++)
    {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.Length; i++)
    {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}
Step by step, in words
  1. The first window: days 1–7. Its 7 days are added one by one: 7 additions, €5430.
  2. Day 8 comes in: +€890. Day 1 goes out: −€820. Days 2–8: €5500, with two operations instead of 7.
  3. Day 9 comes in: +€610. Day 2 goes out: −€640. Days 3–9: €5470, with two operations instead of 7.
  4. Day 10 comes in: +€980. Day 3 goes out: −€910. Days 4–10: €5540, with two operations instead of 7.
  5. Day 11 comes in: +€720. Day 4 goes out: −€700. Days 5–11: €5560, with two operations instead of 7.
  6. Day 12 comes in: +€850. Day 5 goes out: −€580. Days 6–12: €5830, with two operations instead of 7.
  7. 6 windows for 17 operations: 7 for the first and 2 for each next one. From scratch every time it would be 6 · 7 = 42.
The array of sums has length sales.Length - k + 1: that is how many windows there are. The window that ends on day i is at position i - k + 1.

Try it

Predict

The sales for five days and a window of 3 days. What does the program print?

static int[] Slide(int[] sales, int k)
{
    int[] sums = new int[sales.Length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++)
    {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.Length; i++)
    {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}


int[] sales = [820, 640, 910, 700, 580];
int[] sums = Slide(sales, 3);
Console.WriteLine(sums[^1]);
Answer

Try it

Fill in

Day i comes into the window. Which day goes out?

static int[] Slide(int[] sales, int k)
{
    int[] sums = new int[sales.Length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++)
    {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.Length; i++)
    {
        sum += sales[i];
        sum -= sales[];
        sums[i - k + 1] = sum;
    }
    return sums;
}

Try it

Find the bug

The first sum is right, and after it the numbers jump up and down:

int[] sales = [820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850];
int[] sums = Slide(sales, 7);
for (int d = 0; d < sums.Length; d++)
{
    Console.WriteLine($"Days {d + 1}–{d + 7}: €{sums[d]}");
}
Output
Days 1–7: €5430
Days 2–8: €5560
Days 3–9: €5280
Days 4–10: €5650
Days 5–11: €5390
Days 6–12: €5520

Pick the line with the bug.

See it

Measure: from scratch against sliding

The same 10 years and a window of 365 days, and the function counts the additions and subtractions:

static long ops = 0;


static int[] Slide(int[] sales, int k)
{
    int[] sums = new int[sales.Length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++)
    {
        ops++;
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.Length; i++)
    {
        ops++;
        sum += sales[i];
        ops++;
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}
int[] sales = new int[3650];
for (int d = 0; d < sales.Length; d++)
{
    sales[d] = (d * 37) % 101 * 10 + 500;
}
int[] sums = Slide(sales, 365);
Console.WriteLine("Windows: " + sums.Length);
Console.WriteLine("Operations: " + ops);
Console.WriteLine($"The best 365 days: €{sums.Max()}");
Output
Windows: 3286
Operations: 6935
The best 365 days: €366050

6935 operations instead of 1,199,390, and the best 365 days are the same. Run both ways in the browser:

  • Every window from scratch (K = 365) O(n)
  • Sliding: +new −old O(n)
Algorithmn = 1,000n = 3,650n = 10,000n = 100,000
Every window from scratch (K = 365)232,1401,199,3903,517,14036,367,140
Sliding: +new −old1,6356,93519,635199,635
The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.
static int[] Slide(int[] sales, int k)
{
    int[] sums = new int[sales.Length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++)
    {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.Length; i++)
    {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}

The two curves are parallel: the window is always 365 days, so both grow with n. The difference is the factor. From scratch costs k per day, sliding costs 2 per day, however large the window. With a 30-day window sliding is 15 times faster, with 365 days about 180 times.

The idea

A window of variable length

Marketing asks: what is the longest period of consecutive days in which the advertising spend is €400 in total at most? Now the length of the window is not given. It is the answer.

The window has two edges, left and right:

  • right moves forward and adds a new day;
  • if the sum goes over the budget, left moves forward and removes days on the left until the sum is within the budget again;
  • after that the window is allowed, and its length is a candidate for the longest.
static int LongestWithin(int[] spend, int budget)
{
    int best = 0;
    int sum = 0;
    int left = 0;
    for (int right = 0; right < spend.Length; right++)
    {
        sum += spend[right];
        while (sum > budget)
        {
            sum -= spend[left];
            left++;
        }
        best = Math.Max(best, right - left + 1);
    }
    return best;
}
int[] spend = [120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60];
Console.WriteLine("Longest period within €400: " + LongestWithin(spend, 400) + " days");
Output
Longest period within €400: 5 days

There is a loop inside a loop, but this is O(n), not O(n²). left never moves back: every day enters the window once and leaves it at most once. At most 2n moves in total.

This works because the spending is not negative: a longer window is never cheaper. If there are refunds (negative numbers), removing a day on the left may increase the sum, and the rule "shrink until it is within the budget" is no longer right.

See it

No repeated character: a window with a set

Another variable-length window: the longest piece of a log line in which no character repeats. Such pieces give away random tokens that should not be in the log. The window keeps its characters in a set. When the new character is already inside, left removes characters on the left until the repeat is gone:

static string LongestUnique(string line)
{
    var seen = new HashSet<char>();
    int bestStart = 0;
    int bestLen = 0;
    int left = 0;
    for (int right = 0; right < line.Length; right++)
    {
        char c = line[right];
        while (seen.Contains(c))
        {
            seen.Remove(line[left]);
            left++;
        }
        seen.Add(c);
        if (right - left + 1 > bestLen)
        {
            bestLen = right - left + 1;
            bestStart = left;
        }
    }
    return line.Substring(bestStart, bestLen);
}
string line = "GET /cart?token=x9Kq2Lm7Pz&page=2";
string part = LongestUnique(line);
Console.WriteLine($"No repeated character: {part} ({part.Length})");
Output
No repeated character: ?token=x9Kq2Lm7Pz&pag (21)

The check "is it there" in the set is O(1) on average, with a hash table. So here too the total is O(n).

HashSet<char> holds the char values themselves, without boxing.
More precisely, if you are curious

What a "character" is. In Java, C# and JavaScript a string is made of 16-bit units (UTF-16). An emoji such as 🛒 is two such units, and the window will count them separately. In Python a string is made of code points, and 🛒 is one character. A log with Latin letters and digits is the same in all four languages.

The sum must not overflow. int in C# goes up to 2,147,483,647. A year of revenue in cents for a big chain goes past it: then the sum is a long. The counters in the programs above are long for the same reason.

The sum must not drift. If the sales are in euros with cents in a double, every +new −old adds a tiny rounding error, and the errors pile up: after thousands of steps the window's sum is no longer exactly the sum of its days. Keep money in cents, as integers. If the numbers are floating point by nature (temperatures, times), compute the window from scratch every few thousand steps.

The average and the largest. The moving average is the sum divided by k. The largest value in the window does not work with +new −old: a maximum cannot be "subtracted". For it there is a sliding window with a double-ended queue (deque) that keeps the candidates for the maximum.

Exercise

The shortest period with revenue of at least €3500

Solve the task in your editor.

The shortest period. The sales for 12 days are €820, €640, €910, €700, €580, €1020, €760, €890, €610, €980, €720 and €850. What is the shortest period of consecutive days with revenue of at least €3500? The window grows to the right, and while the sum is at least €3500, remember its length if it is smaller, and shrink it from the left.

Output
Shortest period with at least €3500: 5 days (from day 1 to day 5)

More tasks

  • The best week. With sliding, find which 7 consecutive days have the largest revenue and print them.
  • A moving average. Print the average sales for every 7 days, rounded to the cent.
  • Different customers per hour. The orders are sorted by minute, each with a customer number. For every 60-minute window, how many different customers are there? Keep in a map how many orders each customer has in the window.

Test

Check yourself

1. The sum for days 1–7 is €5430. Day 8 is €890, day 1 is €820. What is the sum for days 2–8?
2. n = 3650 days, window k = 365. How many operations does sliding make?
3. In the budget window, the left edge left never moves back. At most how many times does it move in total?
4. The spending also has refunds: negative numbers. Does the window "longest period within the budget" still work?
5. The window sums are in euros with cents, in a double. Why is it better to keep cents in an integer?

Made by Ivo Gergov as part of Evo Tech's campaign for accessible programming education ·