Sliding window pattern: template and problems

When it applies

Use a window when the answer is a contiguous run and there is a property that breaks as the run grows and can be repaired by dropping elements from the left. Because the left edge never moves backwards, the scan stays linear however often the window resizes.

Signals: "longest substring such that", "subarray with sum at most", "at most k distinct", "minimum window containing".

The template

Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.

lo = 0
for hi, x in enumerate(a):
    add(x)                      # extend the window to the right
    while violates():           # repair it from the left
        remove(a[lo]); lo += 1
    best = max(best, hi - lo + 1)

int lo = 0, best = 0;
for (int hi = 0; hi < (int)a.size(); ++hi) {
    add(a[hi]);
    while (violates()) remove(a[lo++]);
    best = std::max(best, hi - lo + 1);
}

int lo = 0, best = 0;
for (int hi = 0; hi < a.length; hi++) {
    add(a[hi]);
    while (violates()) remove(a[lo++]);
    best = Math.max(best, hi - lo + 1);
}

let lo = 0, best = 0;
for (let hi = 0; hi < a.length; hi++) {
  add(a[hi]);                    // extend right
  while (violates()) remove(a[lo++]);   // repair from the left
  best = Math.max(best, hi - lo + 1);
}

let (mut lo, mut best) = (0usize, 0usize);
for hi in 0..a.len() {
    add(a[hi]);
    while violates() { remove(a[lo]); lo += 1; }
    best = best.max(hi - lo + 1);
}

-- Fold carrying (state, window start, best)
foldl step (empty, 0, 0) (zip [0..] xs)
  where step (st, lo, best) (hi, x) =
          let st'        = add x st
              (st'', lo') = shrink st' lo
          in (st'', lo', max best (hi - lo' + 1))

Problems

Medium15 min

Longest run of distinct characters

The window that grows on the right and shrinks on the left, and the invariant that makes it correct.

Open the problem → Medium15 min

Shortest subarray with a sum at least the target

A window that grows on the right until it qualifies, then shrinks on the left while it still does.

Open the problem →

Or sit a timed interview: a fixed window, limited submissions, and a report at the end.