Search & scan · pattern 2 of 7

Fixed-size sliding window

A window is a stretch of neighboring items. When its length is given, move it one place at a time: one item comes in, one goes out. Update what you know about the window from those two items instead of reading all of it again.

Watch it run in the app

When to use it

Use it when the stretch has a given length, such as any k days in a row, and you track a total or a count, not the largest value.

It belongs to the search & scan group: Move one or two positions across the input so that nothing is looked at more than a few times.

Watch it work

A coffee shop wrote down how many cups it sold on each day. Return the largest number of cups sold in any 3 days in a row.

Input
cups = [4, 6, 3, 7, 2]
k = 3

Output
16

The method

Start with an empty window: its total is 0
The next day comes into the window on the right
Once it is longer than k days, the oldest day goes out
Once it holds k days, keep its total if it is the best
Every window was measured once: return the best total

The run, one moment at a time

Step 1. The window is empty, so its total is 0. No full window has been seen, so the best is 0.
```
cups: 4 6 3 7 2
total: 0
best: 0
```
Step 2. Day 0 comes in with 4 cups. The total is 4. The window has 1 day and needs 3.
```
cups: 4 6 3 7 2  (both at 0)
total: 4
best: 0
```
Step 2. Day 1 comes in with 6 cups. The total is 10. The window has 2 days and needs 3.
```
cups: 4 6 3 7 2  (left at 0, right at 1)
total: 10
best: 0
```
Step 2. Day 2 comes in with 3 cups. The total is 13. The window now has 3 days.
```
cups: 4 6 3 7 2  (left at 0, right at 2)
total: 13
best: 0
```
Step 4. Days 0 to 2 hold 13 cups. That is more than the best, 0, so the best becomes 13.
```
cups: 4 6 3 7 2  (left at 0, right at 2)
total: 13
best: 13
```
Step 2. Day 3 comes in with 7 cups. The total is 20, but the window is 4 days long, one too many.
```
cups: 4 6 3 7 2  (left at 0, right at 3)
total: 20
best: 13
```
Step 3. Day 0 goes out on the left and takes its 4 cups away: 20 - 4 = 16. The window is days 1 to 3.
```
cups: 4 6 3 7 2  (left at 1, right at 3)
total: 16
best: 13
```
Step 4. Days 1 to 3 hold 16 cups. That is more than the best, 13, so the best becomes 16.
```
cups: 4 6 3 7 2  (left at 1, right at 3)
total: 16
best: 16
```
Step 2. Day 4 comes in with 2 cups. The total is 18, but the window is 4 days long, one too many.
```
cups: 4 6 3 7 2  (left at 1, right at 4)
total: 18
best: 16
```
Step 3. Day 1 goes out on the left and takes its 6 cups away: 18 - 6 = 12. The window is days 2 to 4.
```
cups: 4 6 3 7 2  (left at 2, right at 4)
total: 12
best: 16
```
Step 4. Days 2 to 4 hold 12 cups. That is not more than the best, 16, so the best stays.
```
cups: 4 6 3 7 2  (left at 2, right at 4)
total: 12
best: 16
```
Step 5. 3 windows were measured, and each day was added once. The best 3 days in a row are days 1 to 3, with 16 cups.
```
cups: 4 6 3 7 2  (left at 1, right at 3)
total: 12
best: 16
```

The code

The numbered comments are the steps of the method.

JavaScript

function solve(cups, k) {
  // 1. Start with an empty window: its total is 0
  let total = 0;
  let best = 0;
  for (let right = 0; right < cups.length; right++) {
    // 2. The next day comes into the window on the right
    total += cups[right];
    // 3. Once it is longer than k days, the oldest day goes out
    if (right >= k) total -= cups[right - k];
    // 4. Once it holds k days, keep its total if it is the best
    if (right >= k - 1 && total > best) best = total;
  }
  // 5. Every window was measured once: return the best total
  return best;
}

Python

def solve(cups, k):
    # 1. Start with an empty window: its total is 0
    total = 0
    best = 0
    for right in range(len(cups)):
        # 2. The next day comes into the window on the right
        total += cups[right]
        # 3. Once it is longer than k days, the oldest day goes out
        if right >= k:
            total -= cups[right - k]
        # 4. Once it holds k days, keep its total if it is the best
        if right >= k - 1 and total > best:
            best = total
    # 5. Every window was measured once: return the best total
    return best

How to spot it

Asked: The largest total of any k items in a row: The length is given, so only the place of the window changes. Each move adds one item to the total and subtracts one.
Given: A text and a shorter word; every candidate is as long as the word: The word fixes the window's length, even though no number k is given. Slide a window of that length along the text.
Limits: k can be large, so adding up each stretch again is too slow: Adding up every window again costs about n times k steps. Updating the total costs two steps for each move, whatever k is.

Looks like it, but is not

The length of the stretch is not given: you want the longest one that keeps a rule. Use Variable sliding window. There the rule decides when the window grows and when it shrinks. Here the length never changes.
You need the largest or smallest value of every k items in a row. Use Monotonic queue. A total can be corrected when an item leaves. A largest value cannot: when it leaves, you must know which remaining value is the largest.
You need the k largest values of the list, wherever they are. Use Heap of the best k. A window holds neighbors only. The k largest values can be anywhere in the list, so a heap keeps them instead.

Cost and mistakes

Time grows with the number of items, written O(n): each item is added once and subtracted at most once, whatever k is. Extra space is constant, written O(1), for a total; a window of letter counts needs one count for each different letter.

Watch out

The item that goes out is exactly k places behind the item that comes in, at position right - k. Being wrong by one place is the usual mistake here.
Do not use a window before it is full. The first k - 1 items only fill it, so compare totals from position k - 1 on.

In the 150

One problem of the 150 uses it. Naming them gives their method away, so the list is folded.

Show it

Permutation In StringMedium · Sliding Window