patternjavascriptTip

Sliding window: track running state instead of recomputing from scratch

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

sliding windowsubarraysubstringwindow summax subarrayfrequency map

Problem

Problems asking for maximum/minimum subarray of fixed size, or longest substring with a constraint, are often solved with O(n*k) brute force when an O(n) sliding window solution exists.

Solution

Maintain a window with left and right pointers. Add the new element when expanding right, remove the old element when shrinking left. Store only the running aggregate (sum, count, frequency map) — never recompute it from scratch.

Why

Each element enters and exits the window exactly once, giving O(n) time. The key insight is that transitioning from window [i..j] to [i+1..j+1] requires only two operations (remove arr[i], add arr[j+1]).

Gotchas

Variable-size windows need a while loop inside the for loop to shrink until valid
Fixed-size windows are simpler — shrink exactly when window size exceeds k
For 'at most k distinct characters', use a frequency map and track active window size

Code Snippets

Fixed and variable sliding window

// Max sum of subarray of size k — O(n)
function maxSumFixed(arr, k) {
  let sum = arr.slice(0, k).reduce((a, b) => a + b, 0);
  let max = sum;
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    max = Math.max(max, sum);
  }
  return max;
}

// Longest substring with at most k distinct chars — O(n)
function longestKDistinct(s, k) {
  const freq = new Map();
  let lo = 0, best = 0;
  for (let hi = 0; hi < s.length; hi++) {
    freq.set(s[hi], (freq.get(s[hi]) ?? 0) + 1);
    while (freq.size > k) {
      const c = s[lo++];
      freq.set(c, freq.get(c) - 1);
      if (freq.get(c) === 0) freq.delete(c);
    }
    best = Math.max(best, hi - lo + 1);
  }
  return best;
}

Context

Finding optimal subarrays or substrings with a size or constraint condition

Revisions (0)

No revisions yet.