Day 5: Sliding Window Pattern

DAY 5 / 30 · WEEK 1

Goal of the day

• Recognize sliding-window problems: anything about a contiguous subarray or substring.
• Implement both shapes: a fixed-size window and a variable-size (expand/shrink) window.
• Turn a brute-force O(n·k) or O(n²) rescan into a single O(n) pass.

Concept

Imagine looking at a strip of numbers through a physical window frame that only shows 3 at a time. The brute-force way to find, say, the maximum 3-number sum: slide the frame one step, then re-add all 3 numbers you can see — O(k) work per slide, O(n·k) total. The sliding-window trick: when you slide the frame right by one, you already know the sum inside it — you just subtract the number that left on the left edge and add the number that entered on the right edge. One subtraction, one addition, O(1) per slide, O(n) total. You never recompute from scratch.

That’s a fixed-size window. A variable-size window works the same “track what enters and leaves” idea, but the frame itself grows and shrinks: you expand the right edge to bring in new elements, and whenever the window breaks some rule (too big a sum, a repeated character), you shrink from the left edge until it’s valid again. Both shapes share the same core move: two pointers marking the window’s edges, and O(1) bookkeeping — not a full rescan — every time either edge moves.

Static diagrams

1. Fixed-size window (size 3)

A fixed-size window of 3 elements sliding right by one: the leaving element is subtracted and the entering element is added, instead of resumming the whole window.

2. Variable-size window (expand / shrink)

A variable-size window expanding to include new characters, then shrinking from the left when a duplicate breaks the no-repeat rule.

Interactive visualizations

leaving / duplicate in window, valid entering / right edge outside window

1. Maximum sum subarray of size k

arr = [4, 2, 5, 1, 3], k = 3

Press Play or Step to begin.

▶ Play⏭ Step↺ Reset🔀 Shuffle

2. Longest substring without repeating characters

s = "abcabcbb"

Press Play or Step to begin.

▶ Play⏭ Step↺ Reset🔀 Shuffle

The code

// --- Shape 1: fixed-size window ---
function maxSumSubarray(arr, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i]; // build the first window once
  let best = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // add entering, subtract leaving
    best = Math.max(best, windowSum);
  }
  return best;
}

// --- Shape 2: variable-size window ---
function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {       // shrink until the duplicate is gone
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);                // now safe to include s[right]
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Line by line:

• maxSumSubarray — the first loop builds the initial window’s sum once (O(k)). Every loop after that does exactly one add and one subtract — O(1) each — instead of re-summing k elements.
• lengthOfLongestSubstring — right always moves forward, one step per outer-loop iteration. The while loop shrinks left (possibly zero times, possibly several) until the window contains no duplicate of s[right]. Because left only ever moves forward too, it can advance at most n times total across the entire function — that’s what keeps this O(n) instead of O(n²), even though there’s a loop inside a loop.

Dry run: maxSumSubarray([4, 2, 5, 1, 3], k = 3)

i	Window	windowSum	best
—	[4, 2, 5]	11 (initial)	11
3	[2, 5, 1]	11 + 1 − 4 = 8	11
4	[5, 1, 3]	8 + 3 − 2 = 9	11

The best 3-element window is the very first one, [4, 2, 5] = 11 — found in one O(k) setup pass plus two O(1) slides, instead of three separate O(k) resums.

Complexity

Approach	Time	Space	Why
Brute force, fixed window (resum every slide)	O(n·k)	O(1)	Every one of ~n windows costs O(k) to sum from scratch.
Sliding window, fixed size	O(n)	O(1)	One O(k) setup, then O(1) per slide.
Brute force, all substrings	O(n²) or worse	O(n)	Checking every substring for a property usually costs at least O(n) each.
Sliding window, variable size — numeric constraint (e.g. running sum)	O(n)	O(1)	left/right each move forward at most n times total; no extra structure needed, just a running number.
Sliding window, variable size — set/map-tracked (e.g. no-repeat characters)	O(n)	O(window size)	Same pointer movement, but the window’s contents must be tracked in a Set/Map sized to whatever’s currently inside it.

Interview corner

• How do you recognize a sliding-window problem? The problem asks about a contiguous subarray or substring — a maximum/minimum sum, a length, or “does a window satisfy some property” (no repeats, sum ≤ target, at most k distinct characters). If it’s about non-contiguous subsequences, sliding window doesn’t apply — look at DP instead (Week 4).

• Fixed vs. variable window — how do you tell which one a problem needs? If the window size is given directly (“subarray of size k”), it’s fixed. If you’re optimizing the window size itself (“longest/shortest subarray such that…”), it’s variable.
  ↳ Common follow-up: “Can you do this with O(1) extra space instead of a Set/Map?” — sometimes, if the constraint is purely numeric (e.g. a running sum), but character/frequency constraints usually need the tracking structure.

• What’s the most common sliding-window bug? Forgetting to shrink the window fully before re-measuring it, or shrinking by a fixed amount instead of by a while loop.
  ⚠ Trap: using if instead of while to shrink only shrinks by one step — if the window is invalid by more than one element, an if leaves it still invalid. Always shrink with a loop that re-checks the condition.

• What if k is bigger than the array’s length? There’s no valid fixed-size window at all — decide (and say out loud) whether that should return 0, -Infinity, or throw, based on what the problem specifies.

How to talk through it out loud: name the window’s invariant before coding — “I’ll expand right to grow the window, and shrink left with a while loop any time the window has a duplicate, so at every point after the inner loop the window is valid.” Stating the invariant is what proves to an interviewer you’re not just pattern-matching syntax you memorized.

Practice problems

1. Maximum Average Subarray I (Easy — LeetCode)

Given an array and an integer k, find the contiguous subarray of length k with the maximum average value.

Show hint

Track the maximum sum with a fixed-size sliding window, and only divide by k once at the very end.

Show solution

function findMaxAverage(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 / k;
}

2. Minimum Size Subarray Sum (Medium — LeetCode)

Given a target sum and an array of positive integers, find the length of the shortest contiguous subarray whose sum is ≥ target. Return 0 if no such subarray exists.

Show hint

Variable window: expand right and add to a running sum; whenever the running sum is ≥ target, that’s a candidate — try shrinking left to see if it’s still ≥ target with a smaller window.

Show solution

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;
}

3. Longest Substring Without Repeating Characters (Medium — LeetCode)

Given a string, find the length of the longest substring without repeating characters.

Show hint

This is today’s second visualization, exactly. Track the characters currently in the window with a Set.

Show solution

function lengthOfLongestSubstring(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;
}

Quiz

Question 1

Sliding window applies to problems about:

Contiguous subarrays/substrings Any subset of elements, in any order Only sorted arrays

Sliding window only works on a contiguous run of elements — that’s exactly what lets you track just the entering/leaving edges.

Question 2

When a fixed-size window slides right by one, what’s the O(1) update?

Subtract the leaving element, add the entering element Re-sum every element in the new window Nothing — the sum never changes

One subtraction for the element leaving, one addition for the element entering — O(1) instead of re-summing the whole window.

Question 3

In a variable-size window, when do you shrink from the left?

Whenever the window becomes invalid (breaks its constraint) On every single step, no matter what Never — only the right edge ever moves

Shrinking is a response to the window breaking its rule — a duplicate appearing, a sum exceeding a limit, etc.

Question 4

Despite having a while loop inside a for loop, why is the variable-window substring pattern O(n) and not O(n²)?

left and right each only ever move forward, at most n steps total combined It’s actually O(n²) — the inner loop is misleading JS engines cache the results automatically

Even though there’s a loop inside a loop, left and right together move forward at most n times total across the whole run — that’s what makes it O(n), not O(n²).

Question 5

Why should you shrink a variable window with a while loop instead of a single if?

The window might need to shrink by more than one step to become valid again while is faster than if in JavaScript There’s no difference, both work identically

A while loop keeps shrinking until the window is valid again, however many steps that takes. An if only shrinks once, which can leave the window still invalid.