Sliding Window: Practice

Sliding Window

A window of elements expands and contracts as it moves across a sequence, reusing work instead of rescanning from scratch.

215132Window sum

8796

Best so far

Loading visual…

Definition

The sliding window technique tracks a contiguous range, or window, over an array or string and updates it incrementally as it moves, instead of recomputing a result from scratch for every possible range. A fixed-size window slides one step at a time: when it moves forward, the value leaving the window is subtracted from a running total, or otherwise removed from whatever state is being tracked, and the value entering the window is added, so each step does a constant amount of work rather than re-summing the whole window. A variable-size window instead grows by moving a right edge forward to include more elements, and shrinks by moving a left edge forward whenever some condition is violated, such as a running sum exceeding a limit or a substring containing a repeated character. Because both edges only ever move forward and each element enters and leaves the window at most once, the whole scan still costs O(n) time even though it explores many different window sizes, turning what looks like an O(n squared) problem, checking every subarray or substring, into a single linear pass.

Examples

function maxSumWindow(nums, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];
  let best = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    best = Math.max(best, windowSum);
  }
  return best;
}
maxSumWindow([2, 1, 5, 1, 3, 2], 3); // 9

The window sum updates by adding the incoming value and subtracting the outgoing one, so sliding across the array costs O(1) per step instead of re-adding all k values.

function longestUnique(s) {
  const seen = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
longestUnique('abcabcbb'); // 3

right expands the window to include new characters; whenever a repeat is found, left shrinks the window from the front until the repeat is gone, keeping every character in the window unique.

function minSubarrayLen(target, nums) {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}
minSubarrayLen(7, [2, 3, 1, 2, 4, 3]); // 2

The window grows until its sum reaches the target, then shrinks from the left as far as possible while still meeting it, tracking the smallest window found along the way.

Common mistakes

Recomputing the window's sum or state from scratch on every slide instead of adjusting it incrementally, which throws away the technique's O(n) advantage.
Forgetting to shrink the left edge when a variable window's condition is violated, so the window grows without bound.
Off by one errors in the window size, such as using right - left instead of right - left + 1 when counting an inclusive window.

Key takeaways

A sliding window updates its running state by adding what enters and removing what leaves, avoiding a full rescan on every step.
Fixed windows always have the same size; variable windows grow and shrink based on a condition.
Both edges only move forward, so the whole scan stays O(n) even though it checks many window positions.
The technique replaces a naive O(n squared) check of every subarray or substring with a single linear pass.

Check your understanding

When a fixed-size window slides one step to the right, what is the cheapest way to update a running sum?

Where you see this

Finding the maximum or average value over a fixed-size trailing window, such as a moving average of recent measurements.
Finding the longest substring or subarray that satisfies a condition, like no repeated characters.
Rate limiting, where a window of recent requests is tracked and old requests age out as new ones arrive.
Network protocols that track an acknowledged range of packets in a sliding window of sequence numbers.

Practice this

Maximum Sum Subarray of Size K (easy)Longest Substring Without Repeating Characters (medium)Minimum Size Subarray Sum (medium)Longest Substring with At Most K Distinct (medium)