Sliding Window

How It Works

Sliding window solves problems about contiguous subarrays or substrings without re-scanning the same elements over and over. Instead of restarting from scratch for every possible window, you maintain a window defined by two pointers — start and end — and slide it across the input one step at a time.

There are two flavors:

• Fixed-size window: the window size k is constant. You add the incoming element, do your calculation, then remove the outgoing element as the window slides forward.
• Dynamic-size window: the window grows by moving end forward, and shrinks by moving start forward whenever a constraint is violated (e.g. too many distinct characters, sum too large).

In both cases, each element enters the window once and leaves it once, so the total work is linear instead of quadratic.

When To Use It

Reach for sliding window when you see these signals in a problem statement:

• It asks for the longest, shortest, maximum, or minimum contiguous subarray or substring.
• A window size k is explicitly given.
• There's a constraint on window contents, like "at most k distinct characters" or "sum less than or equal to target."
• The naive approach would recompute a sum, count, or set for every possible window starting point — that recomputation is exactly what sliding window eliminates.
• The input is a single array or string, and the answer is derived from some contiguous run within it.

Time & Space Complexity

• Time: O(n) — each pointer traverses the array at most once, so total pointer movement is bounded by 2n.
• Space: O(1) for numeric sums, or O(k) when tracking window contents in a hash map/set (e.g. character frequency for "k distinct characters" problems).

Pattern Template

function maxSumSubarrayOfSizeK(arr, k) {
  let windowSum = 0;
  let maxSum = 0;
  let start = 0;

  for (let end = 0; end < arr.length; end++) {
    windowSum += arr[end];

    // Window has reached size k — record and shrink from the left
    if (end >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= arr[start];
      start++;
    }
  }

  return maxSum;
}

For dynamic-size windows, replace the fixed shrink step with a while loop that shrinks start only while the constraint is violated.

Alternative Approaches

• Brute force: check every possible window explicitly, recomputing the sum/count each time — O(n*k) or O(n^2). Always correct, never fast enough for interview-sized constraints.
• Prefix sums: precompute cumulative sums so any range sum is O(1) to query. Useful when you need many arbitrary range queries rather than one sliding pass, but doesn't help when the window also needs to track distinct counts or frequencies.
• Two pointers (non-window): for sorted-array problems like pair sums, plain two pointers is simpler than framing it as a window.

Common Mistakes

• Forgetting to shrink the window when a constraint is violated, leading to an window that grows unbounded.
• Off-by-one errors around whether end and start are inclusive — always trace through a small example by hand.
• Recomputing the window's sum or character counts from scratch on every iteration instead of incrementally updating them, which silently degrades the solution back to O(n^2).
• Using the wrong data structure for window contents — a plain count won't work for "exactly k distinct," which needs a frequency map plus a distinct-count check.

Pattern Summary

Sliding window turns "recompute for every possible window" into "incrementally update as the window moves," collapsing O(n^2) or O(n*k) brute-force solutions into O(n). Look for it whenever a problem talks about contiguous subarrays/substrings with a size or content constraint.