Sliding Window

How sliding window works

Maintain two indices, left and right, defining the window [left, right]. The right edge advances every iteration. The left edge advances when the window violates some condition.

for right in range(n):
    add arr[right] to window
    while window violates constraint:
        remove arr[left] from window
        left += 1
    update answer using current window

Total work — each element is added once (right advances n times) and removed at most once (left advances ≤ n times). O(n) amortized regardless of how often the inner shrinking loop iterates.

Fixed-size vs variable-size windows

	Fixed-size (size k)	Variable-size
Window size	Always exactly k	Depends on a constraint
Left edge	Always lags k positions behind right	Advances only when constraint violated
Common questions	"What's the max/min/sum/avg over any k-window?"	"Longest/shortest subarray satisfying X"
Examples	Moving average, max k-subarray, max k-sliding	Longest no-repeat substring, min window substring
Code complexity	~10 lines	~20 lines

Fixed-window: maximum sum of any k consecutive elements

function maxSumK(arr, k) {
  if (arr.length < k) return null;
  // Sum of first k
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i];
  let maxSum = windowSum;
  // Slide
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k];  // add new, remove old
    if (windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}

The brute force recomputes each window's sum in O(k); total O(n × k). Sliding window updates incrementally — O(1) per shift, O(n) total.

Variable-window: longest substring with no repeating characters

function longestUniqueSubstring(s) {
  const seen = new Map();   // char → last index seen
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (seen.has(c) && seen.get(c) >= left) {
      left = seen.get(c) + 1;  // skip past previous occurrence
    }
    seen.set(c, right);
    if (right - left + 1 > best) best = right - left + 1;
  }
  return best;
}

// "abcabcbb" → 3 ("abc")
// "bbbbb"    → 1 ("b")
// "pwwkew"   → 3 ("wke")

Each character is added to the map once and may cause a left jump once. O(n) total despite the inner conditional.

Variable-window: minimum window substring (LeetCode 76)

Given strings s and t, find the smallest window in s containing all characters of t (with multiplicities). The classic hard sliding-window problem.

function minWindow(s, t) {
  if (s.length < t.length) return '';
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);
  let needCount = need.size;

  const have = new Map();
  let haveCount = 0;
  let left = 0, bestLen = Infinity, bestL = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (need.has(c)) {
      have.set(c, (have.get(c) || 0) + 1);
      if (have.get(c) === need.get(c)) haveCount++;
    }
    // Shrink from left while constraint still holds
    while (haveCount === needCount) {
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestL = left;
      }
      const lc = s[left];
      if (need.has(lc)) {
        have.set(lc, have.get(lc) - 1);
        if (have.get(lc) < need.get(lc)) haveCount--;
      }
      left++;
    }
  }
  return bestLen === Infinity ? '' : s.slice(bestL, bestL + bestLen);
}

Sliding window for streaming and rate limiting

Time-windowed analytics use the same pattern but indexed by timestamp instead of array position. A rate limiter counting requests per minute:

class SlidingWindowRateLimiter {
  constructor(limit, windowMs) {
    this.limit = limit;
    this.windowMs = windowMs;
    this.timestamps = new Map();  // userId → array of timestamps
  }

  allow(userId) {
    const now = Date.now();
    const cutoff = now - this.windowMs;
    let arr = this.timestamps.get(userId) || [];
    // Drop expired entries (slide window)
    while (arr.length && arr[0] <= cutoff) arr.shift();
    if (arr.length >= this.limit) {
      this.timestamps.set(userId, arr);
      return false;
    }
    arr.push(now);
    this.timestamps.set(userId, arr);
    return true;
  }
}

Note — arr.shift() is O(n) in JavaScript. Production rate limiters use deques or sliding-counter approximations to keep operations O(1).

When to use sliding window

• Subarray-with-property questions. "Longest contiguous subarray with sum ≤ X," "longest substring with at most K distinct characters," "minimum window containing all chars of T." If the property is monotonic in window size, sliding window applies.
• Fixed-size window aggregates. Moving averages, k-element sums, max-of-k-window. Standard time-series operation.
• Rate limiting. "At most N actions in the last W seconds." Token bucket, leaky bucket, sliding window — all variants of the same core idea.
• Streaming analytics. Rolling top-k, recent unique users, anomaly detection. Window-indexed by event time.
• Two-pointer-on-string problems. Often the most natural framing.

When sliding window fails

• Non-monotonic constraints. "Longest subarray with sum exactly X" — extending can over- or under-shoot. Use prefix sums + hash map (find pair of prefix sums whose difference is X).
• Negative numbers in "sum at most X" problems. Adding a negative number can satisfy a previously-violated constraint, breaking the monotonic assumption. Use prefix sums or alternative approaches.
• Non-contiguous subsets. Sliding window only works for contiguous subarrays. "Subset with sum X" needs DP, not windowing.
• Tiny n where O(n²) is fine. The sliding-window logic adds overhead; for n < 100 the constant factors of brute force often win.

Common sliding window bugs

• Off-by-one in window size. Window is [left, right] inclusive — size is right - left + 1. Forgetting the +1 produces "longest" answers that are 1 too short.
• Not advancing left in the inner shrink loop. Forgot a left++ at the end of the inner loop = infinite loop.
• Wrong shrink condition. While the constraint is violated, shrink. If only shrinks once — leaves the window in an invalid state if multiple shrinks are needed.
• Forgetting to update the answer in the right place. For longest-with-property, update inside the shrink-while loop. For longest-without-property, update outside. Confusing the two leads to off-by-one or wrong answers.
• Using sliding window on non-monotonic constraints. Some questions look like sliding-window targets but aren't ("subarray with sum exactly X"). Verify monotonicity; if not, use prefix sums + hash map or DP.
• Slow inner-data-structure operations. If the window is a Map and you call .delete() and .set() per shift, that's fine. If it's an array and you use .shift() per shift, that's O(n²). Use a deque or maintain head index.