RoadmapDay 13 / 80
DSAMonth 1 · Week 3

Day 13: Sliding Window Algorithm (Fixed & Dynamic)

Turn "find the best contiguous subarray/substring" brute force into O(n) by growing and shrinking a window instead of re-scanning from scratch.

Mark this day complete

Study

Concepts

Fixed-size window: reuse the previous sum

When the window size k is constant (e.g. "max sum of any k consecutive elements"), compute the first window's sum directly, then slide one step at a time: add the incoming element, subtract the outgoing element. This avoids recomputing the whole sum every step — O(n) instead of O(n·k).

Dynamic window: grow until invalid, then shrink

When the window size varies (e.g. "longest substring without repeating characters", "smallest subarray with sum ≥ target"), expand the right edge to include new elements, and whenever the window violates a constraint, shrink from the left edge until it is valid again. Each element is added once and removed at most once, so total work across the whole run is still O(n), even though it looks nested.

The key mental model: `right` always moves forward every iteration; `left` only moves forward when the window is currently invalid. Neither pointer ever moves backward — that is what makes it linear, not quadratic.

See It

Visualizations

Visualization

Longest substring without repeating characters — "abcabcbb"

Window grows right; when a repeat is found, window shrinks from the left past the duplicate.

a
b
c
a
b
c
b
b
a
b
c
a
b
c
b
b

Build It

Code Examples

Fixed window — max sum of k consecutive elements

js
function maxSumFixedWindow(nums, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];

  let maxSum = windowSum;
  for (let end = k; end < nums.length; end++) {
    windowSum += nums[end] - nums[end - k]; // add incoming, drop outgoing
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

console.log(maxSumFixedWindow([2, 1, 5, 1, 3, 2], 3)); // 9  ([5,1,3])

Dynamic window — longest substring without repeating characters

js
function lengthOfLongestSubstring(s) {
  const lastSeenAt = new Map(); // char -> most recent index
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (lastSeenAt.has(ch) && lastSeenAt.get(ch) >= left) {
      left = lastSeenAt.get(ch) + 1; // jump left past the duplicate
    }
    lastSeenAt.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

console.log(lengthOfLongestSubstring('abcabcbb')); // 3 ("abc")

Remember

Key Takeaways

  • Fixed window: slide by subtracting the outgoing element and adding the incoming one — never resum the whole window.
  • Dynamic window: right always advances; left only advances while the window is invalid — total moves are O(n).
  • Use a Map/Set/frequency-count to track "what is currently inside the window" in O(1) per update.
  • Trigger words: "contiguous subarray/substring", "longest/shortest/max/min window satisfying...".
  • Sliding window is a specialization of two pointers where both pointers only move forward.

Do It

Practice

  1. 1Solve "Minimum Size Subarray Sum" (smallest contiguous subarray with sum ≥ target) with a dynamic window.
  2. 2Solve "Longest Substring with At Most K Distinct Characters" using a frequency Map inside the window.
  3. 3Trace the "abcabcbb" example by hand on paper, writing down left/right/maxLen after every step, before checking the code.