Module F-9·11 min read

Expanding and contracting windows for substring/subarray constraint problems, without recomputation.

Written by Jatin Jain Saraf · Architect of SupraScan

Module F-9 — Sliding Window Pattern

What this module covers: Module F-7's moving average already hinted at this: instead of recomputing a result from scratch for every possible subarray or substring, maintain a "window" and adjust it incrementally as it moves. This module formalizes that into two variants — a fixed-size window and a variable-size window that expands and contracts based on a constraint — both of which turn an O(n × k) or O(n²) brute force into O(n).

The Problem: Recomputing From Scratch Is Wasteful

Say you need the maximum sum of any 3 consecutive elements in an array. The direct approach checks every possible window of size 3, summing each one independently:

// O(n × k) — for every window, sum all k elements from scratch
function maxSumBrute(nums: number[], k: number): number {
  let best = -Infinity;
  for (let i = 0; i <= nums.length - k; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) sum += nums[j]; // recomputes the whole window every time
    best = Math.max(best, sum);
  }
  return best;
}

Every window shares k - 1 elements with the window right before it — only one element enters and one leaves as the window slides forward by one position. Recomputing the full sum from scratch throws away that overlap and redoes work you already did one step ago.

Fixed-Size Window: Maintain a Running Total

The fix mirrors Module F-7's moving average exactly: keep a running sum, add the new element entering the window, subtract the element leaving it.

// O(n) — one pass, constant work per step
function maxSumSliding(nums: number[], k: number): number {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i]; // sum the first window once
 
  let best = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k]; // add the new element, drop the one that just exited
    best = Math.max(best, windowSum);
  }
 
  return best;
}

The first window is summed once, up front. Every window after that costs exactly one addition and one subtraction, regardless of k — the window "slides" one position at a time instead of being recomputed. This is the same window-shift math as the queue's moving average in Module F-7, applied to arrays directly instead of a live stream.

Analogy: A sliding window is a physical picture frame moving across a long mural, one step at a time. You don't repaint what's inside the frame every time you move it — you just note what came into view on one edge and what fell out of view on the other.

Variable-Size Window: Expand and Contract on a Constraint

Not every problem has a fixed window size — often the window needs to grow while some condition holds, and shrink the moment it's violated. The classic example: the longest substring with no repeating characters.

function longestUniqueSubstring(s: string): number {
  const seen = new Set<string>(); // Module F-4 — O(1) membership checks
  let left = 0;
  let best = 0;
 
  for (let right = 0; right < s.length; right++) {
    // Constraint violated: shrink from the left until the duplicate is gone
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
 
  return best;
}
 
longestUniqueSubstring('abcabcbb'); // 3 — "abc"
longestUniqueSubstring('bbbbb');    // 1 — "b"

right only ever moves forward, one step per outer-loop iteration. left also only ever moves forward, and — this is the part worth checking carefully — across the entire run, left can advance at most s.length times in total, even though it's inside a while loop nested inside the for. That's the same "bounded total work across the whole run, despite looking nested" reasoning from the monotonic stack in Module F-6: neither pointer ever moves backward, so the combined work is O(n), not O(n²).