Sliding window

Answer questions about contiguous runs of a list in one pass, by moving two ends forward instead of rechecking every run.

Core pattern. Builds on Hash maps and Two pointers.

Start with the first problem

Draft. This pattern and its problems have not been reviewed by a second person yet.

Many questions ask about a contiguous run of a list: the busiest stretch of a log, the longest series of cheap requests, the shortest part of a trace that touches every service. Checking every run means a start and an end for each one, so the work grows with the square of the list. On a list of 200,000 entries that is billions of steps.

A sliding window keeps one run, between a left and a right index, and moves both ends forward only. The right end takes in the next item. While the run breaks the rule, the left end lets items go. Each item enters once and leaves at most once, so the whole pass is linear.

It works when letting an item go can only make the run more acceptable: removing a timestamp never makes a window wider, removing a non-negative cost never raises a sum. With negative numbers that stops being true, and you need a different idea, such as prefix sums.

Keep a small summary of the window as you go, a count, a sum or a map of counts, and update it as items enter and leave. Never rebuild it from scratch inside the loop; that quietly brings the square back.

Recognise it

  • The answer is about a contiguous run, not any subset.
  • The question says longest, shortest, most or fewest, within some limit.
  • Making the run smaller can only help it meet the limit.

The shape of the code

let left = 0;
let best = 0;
for (let right = 0; right < items.length; right++) {
  // take items[right] into the window's summary
  while (/* the window breaks the rule */ false) {
    // let items[left] go from the summary
    left++;
  }
  best = Math.max(best, right - left + 1);
}
return best;

Problems

In order of difficulty
  1. Not started
  2. Not started
  3. Not started
Esc
↑ ↓ to move↵ to open