ChannelPulse
Coding & data structures · Foundations — reading the problem, and the three pointer patterns

The sliding window

Why a nested loop can be linear, stated as an invariant you can prove in one sentence — then the fixed-size, variable-size, and counting variants, each derived from the same monotonicity argument rather than memorised as three separate templates.

22 min read Free to read Patterns: sliding-window, monotonic-pointer

What you'll be able to do

Before this: complexity-honestly

A sliding window is not a template to memorise. It is a single observation, and once you have the observation the code writes itself.

The observation: if the answer for a range depends only on the elements inside it, and extending the range never makes it more valid, then the left edge never needs to move backwards. That is it. Everything else in this lesson is a consequence.

A window of 3 sliding across "abcabcbb"
abcabcbb
current window (3 wide)

The right edge moves forward n times. The left edge also moves forward, at most n times, and never backwards. Total pointer movement is at most 2n, which is why two nested loops come out linear.

WatchAlgoMasterIO · 07:38

A compact tour of the pattern before the derivation below. Worth watching first for the shape and then ignoring, because the part that decides whether you can use it in an interview — why the two nested loops are actually linear, and what property of the problem the technique depends on — is the part every short summary skips.

Why two nested loops are linear

Write the variable-size window and you will produce something that looks quadratic:

for right in 0..n-1:
    add s[right] to the window
    while window is invalid:
        remove s[left] from the window
        left += 1
    record the best answer

There is a while inside a for. The instinct trained by the previous lesson says O(n²). The instinct is wrong, and knowing exactly why is the point.

Count pointer movements instead of loop nestings. right increments exactly n times, once per outer iteration. left only ever increments, and it can never exceed right, so across the entire run it increments at most n times in total — not n times per outer iteration. Total work is bounded by 2n pointer moves plus O(1) bookkeeping each. O(n).

This is the same accounting trick as the dynamic-array proof in the previous lesson. An individual outer iteration can do O(n) work — one long collapse of the left edge — but the total across all iterations is bounded, so the per-operation average is constant. Amortised analysis, applied to a loop instead of a data structure.

When it applies, and when it does not

A window works when three things hold.

Contiguity. The answer must be a contiguous run. "Longest subarray with sum ≤ k" is a window. "Longest subsequence with sum ≤ k" is not — elements can be skipped, so there is no single left edge to maintain.

Monotone validity. Growing the window must only ever make it less valid, or shrinking must only ever make it more valid. "Sum ≤ k with all-positive elements" satisfies this: adding an element only increases the sum. This is exactly why the classic prompt says positive integers.

Cheap incremental update. Adding one element and removing one element must both be O(1) or close to it — a running sum, a count map, a max in a monotonic deque.

Variant one: fixed size

The easiest case. The window is always exactly k wide, so there is no while at all — one element enters and one element leaves on every step.

1Build the first window, then roll it▾
JavaScript
// Maximum sum of any k consecutive elements.
function maxSumOfK(nums, k) {
  if (k <= 0 || nums.length < k) return null;

  // The first window is the only one we compute from scratch.
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;

  // Every later window is the previous one, plus the entrant, minus the leaver.
  for (let right = k; right < nums.length; right++) {
    sum += nums[right] - nums[right - k];
    best = Math.max(best, sum);
  }
  return best;
}

console.log(maxSumOfK([2, 1, 5, 1, 3, 2], 3));   // 9  -> [5,1,3]
console.log(maxSumOfK([2, 3], 3));               // null -> shorter than k
console.log(maxSumOfK([-1, -2, -3, -4], 2));     // -3 -> negatives are fine here

Both tabs are the same algorithm, and the differences are the ones worth knowing. window is not called sum in the Python because sum is the built-in the first line uses. range(k, len(nums)) is the one place a Python index loop is the honest choice — the loop body needs nums[right - k] as well as nums[right], so there is nothing to enumerate over. And the absent answer prints as None, not null: same idea, and both languages let it fall out of the function untyped, which an interviewer may well push back on. "I'd return None and document it, or raise, depending on the caller" is the answer.

Note that negative numbers are fine for the fixed-size variant. The monotonicity requirement only bites when the window size is decided by validity. With a fixed k there is no validity test, so there is nothing to be non-monotone about. This distinction is worth being able to state — it is the difference between a rule and a memorised warning.

2Recognise the disguises▾

Fixed-size windows appear in prompts that never say "window": maximum average of k consecutive readings, number of k-length substrings with all distinct characters, the rolling hash step of Rabin–Karp, moving averages over a metrics stream. Each is enter-one-leave-one over a running aggregate.

Variant two: variable size, longest valid

Now the window grows greedily and shrinks only under duress. The invariant is: after each iteration, the window [left, right] is valid.

3Grow on the right, repair on the left▾
JavaScript
// Longest subarray whose sum is at most `limit`. Requires non-negative values --
// see the pitfall above for why.
function longestAtMostSum(nums, limit) {
  let left = 0;
  let sum = 0;
  let best = 0;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    // Repair the invariant. `while`, not `if`: one entrant can force several
    // departures. `left <= right` keeps us safe when a single element exceeds
    // the limit on its own.
    while (sum > limit && left <= right) {
      sum -= nums[left];
      left++;
    }

    best = Math.max(best, right - left + 1);
  }
  return best;
}

console.log(longestAtMostSum([1, 2, 1, 0, 1, 1, 0], 4));  // 5
console.log(longestAtMostSum([9, 1, 1], 4));              // 2  -> the 9 is skipped past
console.log(longestAtMostSum([], 4));                     // 0

Two details in that code are the ones interviewers probe.

while rather than if: adding a single large element can require evicting several small ones. An if handles one eviction and leaves the invariant broken — a bug that passes [1,2,1,0,1,1,0] and fails [9,1,1], which is precisely why step 3 of the first lesson insists on an adversarial example.

left <= right: when one element alone exceeds the limit, the loop must be able to shrink the window to empty rather than running left past right and computing a negative width.

4Change the validity test, keep the skeleton▾

The skeleton is now fixed. Every "longest valid window" problem is the same nine lines with a different add, remove, and isInvalid. Here is the distinct-characters problem from the first lesson, written in the same shape with a count map:

JavaScript
function longestUniqueWindow(s) {
  const count = new Map();
  let left = 0;
  let best = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    count.set(ch, (count.get(ch) ?? 0) + 1);

    // Invalid means: the character we just added is now present twice. Because we
    // repair after every single addition, at most one character can be over count,
    // so shrinking until THIS character's count drops to 1 is sufficient.
    while (count.get(ch) > 1) {
      const out = s[left];
      count.set(out, count.get(out) - 1);
      left++;
    }

    best = Math.max(best, right - left + 1);
  }
  return best;
}

for (const s of ["abcabcbb", "bbbbb", "tmmzuxt", "", "pwwkew"]) {
  console.log(`${JSON.stringify(s).padEnd(10)} -> ${longestUniqueWindow(s)}`);
}

Compare this to the map-of-last-index version in the first lesson. Both are O(n) and both are correct; this one generalises (swap the validity test and you have "at most two distinct characters"), while that one is slightly faster because left jumps in one move instead of stepping. Being able to present both, and say which you would ship and why, is the answer to "can you do better?" done properly.

Variant three: shortest valid, and the inversion

Longest-valid and shortest-valid look symmetric but the code differs in one important way: you record the answer in a different place.

For longest valid, the window is valid after the repair loop, so you record after it. For shortest valid, the window becomes valid during shrinking, so you record inside the shrink loop, before the window stops being valid.

JavaScript
// Shortest subarray with sum >= target. Non-negative values.
function shortestAtLeastSum(nums, target) {
  let left = 0;
  let sum = 0;
  let best = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    // Now the loop condition is "still valid", and we record inside it: each
    // iteration we have a valid window, and we shrink to look for a smaller one.
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

console.log(shortestAtLeastSum([2, 3, 1, 2, 4, 3], 7));  // 2 -> [4,3]
console.log(shortestAtLeastSum([1, 1, 1], 7));           // 0 -> impossible

Variant four: exactly-k, via at-most-k

This is the transformation that turns a genuinely hard counting problem into two applications of something you already have — and it is the one that separates candidates who understand the pattern from those who memorised it.

"Count the subarrays with exactly k distinct values" is awkward as a window, because "exactly k" is not monotone: growing a window can push the count above k and shrinking can push it below, so there is no single valid range per right edge.

"Count the subarrays with at most k distinct values" is monotone, and it is a three-line variation on the skeleton above. And:

exactly(k) = atMost(k) - atMost(k - 1)

Every subarray with at most k distinct values either has at most k−1, or has exactly k. Subtract and the exactly-k count falls out.

JavaScript
function atMostKDistinct(nums, k) {
  if (k <= 0) return 0;
  const count = new Map();
  let left = 0;
  let total = 0;

  for (let right = 0; right < nums.length; right++) {
    count.set(nums[right], (count.get(nums[right]) ?? 0) + 1);

    while (count.size > k) {
      const out = nums[left];
      const c = count.get(out) - 1;
      if (c === 0) count.delete(out);
      else count.set(out, c);
      left++;
    }

    // KEY STEP: every window ending at `right` and starting anywhere in
    // [left, right] is valid, and there are (right - left + 1) of them. Counting
    // by right-endpoint like this is how you count subarrays without listing them.
    total += right - left + 1;
  }
  return total;
}

const exactlyKDistinct = (nums, k) => atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);

const nums = [1, 2, 1, 2, 3];
console.log(`atMost(2) = ${atMostKDistinct(nums, 2)}`);
console.log(`atMost(1) = ${atMostKDistinct(nums, 1)}`);
console.log(`exactly(2) = ${exactlyKDistinct(nums, 2)}`);  // 7

The del in the Python tab is the trap. Map.delete in the JavaScript version is obviously required because Map.size counts keys; Counter makes the decrement so comfortable that leaving a zero behind is easy to miss, and len(count) then reports a distinct-value count that includes characters no longer in the window. count.total() would still be right; len(count) would not. Deleting at zero is the fix in both languages, and knowing why is the difference between typing the line and understanding the invariant it protects.

The total += right - left + 1 line is worth more than the transformation itself. Counting valid subarrays by their right endpoint — "how many valid windows end here?" — is a technique that reappears throughout counting problems, and it is O(n) where enumerating the subarrays is O(n²).

The checklist

Before writing a window, answer these four questions out loud. They map exactly onto the three preconditions plus the variant choice.

  1. Is the answer contiguous? If no, this is not a window problem.
  2. Is validity monotone in the window's size — and specifically, are there negatives or other non-monotone values that break it?
  3. Can I add and remove one element in O(1)? What structure holds the window state — a running sum, a count map, a monotonic deque?
  4. Am I collecting the longest, the shortest, or a count? That decides whether my while tests invalidity or validity, and where I record the answer.