Sliding Window

Your step counter logged a week of walking, in thousands of steps: 4, 2, 7, 1, 8, 3, 5. You want your best stretch of 3 days in a row. The obvious way is to add up days 1 to 3, then days 2 to 4, then days 3 to 5, and so on, each time from scratch.

Look at two neighbouring sums. Days 1 to 3 are 4 + 2 + 7. Days 2 to 4 are 2 + 7 + 1. The 2 + 7 in the middle is shared. Only one day left and one day arrived. So instead of re-adding everything, take the old sum, subtract the day that left, and add the day that arrived.

#The idea: a frame that slides

Picture a frame laid over the array that covers a run of neighbouring items: a window. You keep a summary of what is inside it, such as a sum, a count or a set. When the window slides one step right, exactly one item enters and at most one leaves, so you update the summary with two small changes instead of rebuilding it.

#Fixed-size windows

When the window size k is fixed, the recipe is short. Add up the first k items. Then, for each new item, add it and subtract the item k places behind it.

sum = steps[0] + ... + steps[k - 1]best = sumfor right from k to n - 1:  sum += steps[right] - steps[right - k]  best = max(best, sum)

// Largest sum of k neighbouring items. Assumes 1 <= k <= nums.length.
function bestWindowSum(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let right = k; right < nums.length; right++) {
    sum += nums[right] - nums[right - k]; // one in, one out
    best = Math.max(best, sum);
  }
  return best;
}
 
bestWindowSum([4, 2, 7, 1, 8, 3, 5], 3); // 16

# Largest sum of k neighbouring items. Assumes 1 <= k <= len(nums).
def best_window_sum(nums, k):
    total = sum(nums[:k])
    best = total
    for right in range(k, len(nums)):
        total += nums[right] - nums[right - k]  # one in, one out
        best = max(best, total)
    return best
 
best_window_sum([4, 2, 7, 1, 8, 3, 5], 3)  # 16

#Windows that grow and shrink

Often the size is not given. The question is "the longest run that obeys a rule" or "the shortest run that reaches a goal". Then the window's two edges move separately, like the same-direction shape in Two Pointers:

1. Look at the next item, at right.
2. If taking it in would break the rule, move left forward, removing items, until it would not.
3. Take the item in. The window is valid, so record its length if it is the best so far.

Example: find the longest run of letters in "streets" with no letter repeated. The summary is a set of the letters inside the window, so "is this letter already in the window?" costs O(1).

for right from 0 to n - 1:  while s[right] is in window:    remove s[left] from window; left += 1  add s[right] to window  best = max(best, right - left + 1)

function longestNoRepeat(s) {
  const inWindow = new Set();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    while (inWindow.has(s[right])) { // shrink until the rule holds
      inWindow.delete(s[left]);
      left++;
    }
    inWindow.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
 
longestNoRepeat("streets"); // 4

def longest_no_repeat(s):
    in_window = set()
    left = 0
    best = 0
    for right in range(len(s)):
        while s[right] in in_window:  # shrink until the rule holds
            in_window.remove(s[left])
            left += 1
        in_window.add(s[right])
        best = max(best, right - left + 1)
    return best
 
longest_no_repeat("streets")  # 4

The while inside the for looks like O(n²), but count the moves of left over the whole run. It only goes forward and never passes right, so it moves at most n times in total.

#Common mistakes

#Check yourself

#What to practise next

A window answers questions about runs as it slides past them. When you need the sum of many different runs, in any order, or the numbers can be negative, Prefix Sums answers each one in O(1) after a single pass.