Fixed-Size Sliding Window: Rolling Sums and Counts, Step by Step

One in, one out

When every window has the same length k, consecutive windows overlap in k − 1 elements. The step from [i, i + k − 1] to [i + 1, i + k] adds one element and removes one, so any state that can absorb one addition and one removal moves along the array in O(1) per step. Recomputing each window from scratch costs O(nk); rolling it costs O(n).

The best total over 3 consecutive days in [2, 1, 5, 1, 3, 2].

Step 1 / 4

nums
20lo1152hi133425
sum8best8
Build the first window, days 0 to 2: total 8. It is the best so far.
Step 2 / 4

nums
2011lo5213hi3425
sum7best8
Slide right: add 1, drop 2. The total is 7; the best stays 8.
Step 3 / 4

nums
201152lo1334hi25
sum9best9
Slide right: add 3, drop 1. The total is 9, a new best.
Step 4 / 4

nums
20115213lo3425hi
sum6best9
Slide right: add 2, drop 5. The total is 6; the best stays 9.

The code

Build the first window, then slide. The best starts at the first window's total, not at zero, because every window may be negative.

def max_sum_k(nums, k):
    total = sum(nums[:k])            # the first window
    best = total
    for i in range(k, len(nums)):
        total += nums[i] - nums[i - k]   # one in, one out
        best = max(best, total)
    return best

#include <vector>
#include <algorithm>

long long solve(const std::vector<int>& nums, int k) {
    long long total = 0;
    for (int i = 0; i < k; ++i) total += nums[i];          // the first window
    long long best = total;
    for (int i = k; i < (int)nums.size(); ++i) {
        total += nums[i] - nums[i - k];                    // one in, one out
        best = std::max(best, total);
    }
    return best;
}

class Solution {
    public long maxSumK(int[] nums, int k) {
        long total = 0;
        for (int i = 0; i < k; i++) total += nums[i];      // the first window
        long best = total;
        for (int i = k; i < nums.length; i++) {
            total += nums[i] - nums[i - k];                // one in, one out
            best = Math.max(best, total);
        }
        return best;
    }
}

function maxSumK(nums, k) {
  let total = 0;
  for (let i = 0; i < k; i++) total += nums[i];   // the first window
  let best = total;
  for (let i = k; i < nums.length; i++) {
    total += nums[i] - nums[i - k];               // one in, one out
    best = Math.max(best, total);
  }
  return best;
}

fn solve(nums: &[i64], k: usize) -> i64 {
    let mut total: i64 = nums[..k].iter().sum();   // the first window
    let mut best = total;
    for i in k..nums.len() {
        total += nums[i] - nums[i - k];            // one in, one out
        best = best.max(total);
    }
    best
}

-- Each later window total is the previous one plus the element entering minus the one leaving.
solve :: [Int] -> Int -> Int
solve xs k = maximum (scanl step first (zip (drop k xs) xs))
  where
    first = sum (take k xs)
    step total (new, old) = total + new - old

The same code is the reference solution to Best total over k consecutive days, where it is compiled and run against the tests in all six languages.

Counts instead of a sum

When the question is about which letters a window holds, the state is a table of counts. Anagrams are the standard case: a window of length |p| is an anagram of p exactly when its counts equal p's. Comparing 26 counts after every step would work, but there is a tidier state. Keep need[c], p's count minus the window's, and off, the number of letters with nonzero need. An update changes one entry of need, so off changes by at most one, and the window is an anagram exactly when off = 0.

Every start of an anagram of "abc" in "cbaebabacd".

Step 1 / 10

s
c0lo/hib1a2e3b4a5b6a7c8d9
off2found[]
'c' enters. The window is not full yet.
Step 2 / 10

s
c0lob1hia2e3b4a5b6a7c8d9
off1found[]
'b' enters. The window is not full yet.
Step 3 / 10

s
c0lob1a2hie3b4a5b6a7c8d9
off0found[0]
'a' enters. Every count matches (off = 0): "cba" is an anagram, so record 0.
Step 4 / 10

s
c0b1loa2e3hib4a5b6a7c8d9
off2found[0]
'e' enters. 'c' leaves. 2 letters still differ.
Step 5 / 10

s
c0b1a2loe3b4hia5b6a7c8d9
off2found[0]
'b' enters. 'b' leaves. 2 letters still differ.
Step 6 / 10

s
c0b1a2e3lob4a5hib6a7c8d9
off2found[0]
'a' enters. 'a' leaves. 2 letters still differ.
Step 7 / 10

s
c0b1a2e3b4loa5b6hia7c8d9
off2found[0]
'b' enters. 'e' leaves. 2 letters still differ.
Step 8 / 10

s
c0b1a2e3b4a5lob6a7hic8d9
off2found[0]
'a' enters. 'b' leaves. 2 letters still differ.
Step 9 / 10

s
c0b1a2e3b4a5b6loa7c8hid9
off0found[0, 6]
'c' enters. 'a' leaves. Every count matches (off = 0): "bac" is an anagram, so record 6.
Step 10 / 10

s
c0b1a2e3b4a5b6a7loc8d9hi
off2found[0, 6]
'd' enters. 'b' leaves. 2 letters still differ.

The same "how many entries are still wrong" counter turns any comparison of two count tables into an O(1) test. It reappears in the shortest-window module, where the window must cover a pattern.

Fixed-size windows

One in, one out

The code

Counts instead of a sum

Problems in this module