Sliding window

The insight: don't recompute, adjust

A brute-force "every contiguous subarray/substring" solution recomputes each window from scratch — O(n) work, done for O(n) windows, is O(n²). Sliding window notices that consecutive windows overlap almost entirely: moving from [i, j] to [i+1, j+1] only removes one element and adds one element. Update the running answer instead of rebuilding it, and the whole scan collapses to O(n).

Fixed-size window

// max sum of any window of size k — O(n) time, O(1) space
function maxSumWindow(nums, k) {
  if (k < 1 || k > nums.length) return null; // no window of that size exists; 0 would look like a real sum
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i]; // build first window

  let best = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k]; // add new, drop old — O(1)
    best = Math.max(best, windowSum);
  }
  return best;
}

Variable-size window — the more common interview shape

Here the window grows on the right and shrinks from the left based on a condition, instead of staying a fixed size. This is the pattern behind "longest substring without repeating characters," "smallest subarray with sum ≥ target," and most "longest/shortest X satisfying Y" questions.

// longest substring with no repeated characters — O(n) time, O(min(n, alphabet)) space
function longestUniqueSubstring(s) {
  const lastSeen = new Map(); // char → most recent index
  let left = 0, best = 0;

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

Notice left only ever moves forward — it never resets to 0 and re-scans. That "each pointer visits each index at most once" property is why this is O(n) and not O(n²) despite looking like a nested loop conceptually.

Dry run: longestUniqueSubstring("abcabcbb")

left jumps straight to one past the repeat's last position — never one step at a time, never backward. Across all 8 steps, left moved a total of 7 positions, not 7 positions per step — that's the amortized O(n) at work.

The general variable-window template

function template(arr, condition) {
  let left = 0;
  let state = /* running total, count, or map */ 0;

  for (let right = 0; right < arr.length; right++) {
    // 1. expand: fold arr[right] into state

    while (/* state violates the condition */ false) {
      // 2. shrink: undo arr[left] from state, then left++
      left++;
    }

    // 3. update the answer using the current valid window [left, right]
  }
}

See the window move

Watch left jump rather than crawl. That jump is what keeps the whole scan linear even though the window shrinks and grows.

Longest or shortest: where the answer is recorded

The template above has one open slot: "update the answer using the current valid window." Where you fill it depends on whether you want the longest or the shortest valid window, and getting it wrong is the most common way to write a window that looks right and is off by one.

• Longest valid window. Expand, then shrink until the window is valid again, then record. The window is valid at the moment you read its length, and it is as large as it can be for this right end.
• Shortest valid window. Expand until the window becomes valid, then record inside the shrink loop and keep shrinking for as long as it stays valid. Every valid window you pass on the way down is a candidate, and the last one is the shortest for this right end.

The classic shortest case is the minimal-length subarray whose sum is at least target, for an array of positive numbers.

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) {                       // valid: record, then try a shorter one
      best = Math.min(best, right - left + 1);
      sum -= nums[left++];
    }
  }
  return best === Infinity ? 0 : best;            // no valid window: 0, not Infinity
}

Dry run: minSubArrayLen(7, [2, 3, 1, 2, 4, 3])

Why left never has to move backward: with positive numbers, if the window [l, r] already reaches the target, so does [l, r + 1]. The latest start that still reaches the target (the one that gives the shortest window for that right end) can only move right as right grows, so each index is added once and removed at most once. Time O(n), space O(1).

Counting windows: every right end adds right − left + 1

Some questions ask how many subarrays satisfy a rule, not how long the best one is. Take: how many contiguous subarrays of a positive-integer array have a product strictly less than k?

Fix the right end and let left be the smallest start that keeps the product below k. Shrinking a window of positive numbers never increases its product, so every start from left to right is also valid, and no start before left is. That is exactly right - left + 1 valid subarrays ending at right. Add that number at each step and every valid subarray is counted exactly once, grouped by where it ends.

function numSubarrayProductLessThanK(nums, k) {
  if (k <= 1) return 0;                          // products of positive integers are at least 1
  let left = 0, product = 1, count = 0;
  for (let right = 0; right < nums.length; right++) {
    product *= nums[right];
    while (product >= k) product /= nums[left++];
    count += right - left + 1;                    // all starts in [left, right] work
  }
  return count;
}

This is k = 100 on [10, 5, 2, 6]. Time O(n), space O(1). The k <= 1 guard is not decoration: with k = 1 the loop condition stays true after every element has been divided out, left runs past the end of the array, and the count comes out wrong (-1 for [5] with k = 1). The division is exact here because product is always a product of the numbers in the window, as long as it stays below 2⁵³.

At most K distinct: a longest window over a counting map

"Longest substring with at most K distinct characters" (and "fruit into baskets", which is the same question with K = 2) needs the window to know how many of each thing it holds, not just a total. A Map from item to count does it, and its size is the number of distinct items.

function longestAtMostKDistinct(s, k) {
  const counts = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    while (counts.size > k) {
      const c = s[left++];
      counts.set(c, counts.get(c) - 1);
      if (counts.get(c) === 0) counts.delete(c);  // without this, size never drops
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

This is k = 2 on "eceba". Each character enters once and leaves at most once: O(n) time, and the map holds at most k + 1 keys, so O(k) space. With k = 0 the shrink loop empties the window every time and the answer is 0, which is correct for an empty allowance. The "fruit" version is the same code over an array of numbers.

Exactly K is at most K minus at most K − 1

Now ask for the number of subarrays with exactly K distinct values. The window machinery cannot answer this directly, because "exactly K" is not monotone: a window with exactly K distinct values can lose one when you shrink it, and gain one when you expand it, so neither pointer has a reliable direction. "At most K" does behave: shrinking never increases the distinct count, so the valid windows for a given right end are exactly the starts from left to right.

function subarraysWithKDistinct(nums, k) {
  return atMostKDistinct(nums, k) - atMostKDistinct(nums, k - 1);
}

function atMostKDistinct(nums, k) {
  const counts = new Map();
  let left = 0, total = 0;
  for (let right = 0; right < nums.length; right++) {
    counts.set(nums[right], (counts.get(nums[right]) || 0) + 1);
    while (counts.size > k) {
      const x = nums[left++];
      counts.set(x, counts.get(x) - 1);
      if (counts.get(x) === 0) counts.delete(x);
    }
    total += right - left + 1;
  }
  return total;
}

On [1, 2, 1, 2, 3] with K = 2: 12 − 5 = 7 subarrays have exactly two distinct values. Two linear passes, so O(n) time. The same subtraction counts subarrays whose sum equals a goal when the numbers are non-negative: atMostSum(goal) - atMostSum(goal - 1), and "nice" subarrays with exactly K odd numbers once each element is replaced by x % 2.

function numSubarraysWithSum(nums, goal) {
  return atMostSum(nums, goal) - atMostSum(nums, goal - 1);
}

function atMostSum(nums, s) {
  if (s < 0) return 0;                          // no non-negative sum is below zero
  let left = 0, sum = 0, total = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum > s) sum -= nums[left++];
    total += right - left + 1;
  }
  return total;
}

The need and missing counters: minimum window substring

Given strings s and t, find the shortest window of s that contains every character of t, counting repeats: if t has two As, the window needs two. This is the template's hardest everyday use, and it is easiest if you keep one idea in your head.

For each character, store need[c] = how many copies of c the window still lacks. It starts at the count in t. Adding a character to the window subtracts one; removing one adds one. A positive value means the window is still short of that character; zero or below means it has enough, and a negative number is a surplus. To avoid scanning the whole map after every step, keep one more number, missing: the total of the positive parts, starting at t.length. The window is valid exactly when missing === 0.

function minWindow(s, t) {
  if (t.length === 0 || t.length > s.length) return "";
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) || 0) + 1);

  let missing = t.length;
  let left = 0, bestStart = 0, bestLen = Infinity;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    if (need.has(c)) {
      if (need.get(c) > 0) missing--;            // this copy was still needed
      need.set(c, need.get(c) - 1);
    }
    while (missing === 0) {                       // valid: record, then try to shrink
      if (right - left + 1 < bestLen) {
        bestLen = right - left + 1;
        bestStart = left;
      }
      const d = s[left++];
      if (need.has(d)) {
        need.set(d, need.get(d) + 1);
        if (need.get(d) > 0) missing++;          // we just gave up a copy we needed
      }
    }
  }
  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);
}

Dry run: minWindow("ADOBECODEBANC", "ABC")

Each index enters the window once and leaves at most once, and each step is an O(1) map operation: O(|s| + |t|) time. The map holds only the distinct characters of t, so the space is O(number of distinct characters in t). Because the comparison is strict, ties keep the first shortest window.

Fixed window with a frequency compare: anagrams and permutations

"Find every start index where an anagram of p appears in s", and "does s2 contain a permutation of s1", are fixed windows of length k = p.length. The window is valid when its character counts equal the counts of p. The code assumes lowercase letters, to keep the indexing simple. Comparing two 26-slot arrays each step costs O(26) per step, which is fine, but you can make each slide O(1) by tracking only the difference and a counter of how many letters still differ.

function findAnagrams(s, p) {
  const out = [];
  const k = p.length;
  if (k > s.length) return out;
  const diff = new Array(26).fill(0);           // window count minus pattern count, per letter
  let unequal = 0;                              // how many letters have diff !== 0

  function bump(ch, delta) {
    const i = ch.charCodeAt(0) - 97;
    if (diff[i] === 0) unequal++;
    diff[i] += delta;
    if (diff[i] === 0) unequal--;
  }

  for (const ch of p) bump(ch, -1);
  for (let right = 0; right < s.length; right++) {
    bump(s[right], 1);
    if (right >= k) bump(s[right - k], -1);     // the letter that just left the window
    if (right >= k - 1 && unequal === 0) out.push(right - k + 1);
  }
  return out;
}

function checkInclusion(s1, s2) {
  return findAnagrams(s2, s1).length > 0;
}

This is s = "cbaebabacd" and p = "abc", which gives [0, 6]. Time O(|s| + |p|) and space O(1) for 26 lowercase letters. For a larger alphabet, use a Map and delete entries whose count reaches zero, and keep the same counter idea. An anagram and a permutation are the same thing here, since both mean "same letters, same counts, any order"; a sorted copy or a fresh count at each window would also work but costs O(k) per window.

A budget window: replace K characters, flip K zeros

A third kind of validity is a budget: the window may contain at most K things that are "wrong" and need fixing. Max consecutive ones III allows flipping at most K zeros, so a window is valid when it contains at most K zeros. That is the "at most" window again, with a counter instead of a map.

function longestOnes(nums, k) {
  let left = 0, zeros = 0, best = 0;
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] === 0) zeros++;
    while (zeros > k) {
      if (nums[left] === 0) zeros--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Longest repeating character replacement is the same budget with a twist. You may replace up to K characters so the window becomes one repeated letter. In a window of length len, you keep the most frequent letter and replace the rest, which costs len - maxCount replacements. The window is valid when that cost is at most K.

function characterReplacement(s, k) {
  const counts = new Array(26).fill(0);        // uppercase A-Z
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    counts[s.charCodeAt(right) - 65]++;
    while (right - left + 1 - Math.max(...counts) > k) {
      counts[s.charCodeAt(left) - 65]--;
      left++;
    }
    best = Math.max(best, right - left + 1);
  }
  return best;
}

This is "AABABBA" with K = 1, answer 4. The Math.max(...counts) scan costs 26 operations, so the total is O(26 · n), which is O(n). A well-known variant keeps maxCount as a running maximum that is never lowered, and replaces the while with an if, so the window never gets smaller. That version is correct and avoids the scan, but its proof takes a paragraph, so write the scanning version first and mention the variant only if asked about the constant factor.

When the window breaks: negative numbers and non-monotone rules

Every window above rests on one property: validity is monotone. If a window is valid, so are the windows you get by shrinking it (for the "at most" rules), or growing it (for the "at least" rules), and moving left forward therefore never throws away an answer. Lose the property and the pointers stop knowing which way to go.

The usual way to lose it is a negative number. Run the shortest-window template on "shortest subarray with sum at least k" for [84, -37, 32, 40, 95] and k = 167:

// WRONG when nums can be negative
function shortestSubarrayWrong(nums, k) {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= k) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left++];
    }
  }
  return best === Infinity ? -1 : best;
}

It returns 5: at the last element the sum is 214, the whole array is recorded, and removing the 84 drops the sum to 130, below 167, so the loop stops. But the window [32, 40, 95] sums to exactly 167 and has length 3. To reach it you would have to remove the -37 as well, and removing a negative raises the sum, which the loop never tries because it stopped the moment the sum dropped.

The interview habit that saves you: before you commit to a window, ask "if this window is valid, what happens when I add an element, and when I remove one?" If the answer depends on the sign or the value of what you add, stop and reach for prefix sums.

Sliding window maximum: a window with a deque

So far the state could be updated in O(1) in both directions: a sum is undone by subtraction, a count by decrementing. A maximum cannot be undone. When the largest element leaves the window, you need the largest of what is left, and nothing in a single running number tells you that. The brute force rescans each window, O(n · k).

Keep only the elements that could still become the maximum. Suppose a new element x arrives and an earlier element in the window is smaller than or equal to x. That earlier element can never be the maximum again, because x is at least as large and leaves the window later. So throw it away. What survives is a list of indices whose values decrease from front to back, and the front is always the maximum of the window. Two more rules finish it: drop the front when its index falls out of the window, and read the front after each full window. The list needs removal at both ends, which is a deque. (Assume 1 <= k <= nums.length.)

function maxSlidingWindow(nums, k) {
  const out = [];
  const dq = [];            // indices; the live part starts at head, values decrease
  let head = 0;
  for (let i = 0; i < nums.length; i++) {
    while (dq.length > head && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();  // dominated by nums[i]
    dq.push(i);
    if (dq[head] <= i - k) head++;            // the front index left the window
    if (i >= k - 1) out.push(nums[dq[head]]);
  }
  return out;
}

Dry run: maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)

Each index is pushed once and popped at most once, so the loop does O(n) work in total even though the inner while can pop many entries at one step. The live part holds at most k indices. Using a head index avoids shift(), which the language defines as moving every remaining element down one place, so you should not count on it being O(1) when you explain the complexity. Popping on <= rather than < keeps the deque strictly decreasing and is safe for equal values, since the newer one lasts longer. The same two-ended structure answers "longest subarray where max minus min is at most a limit" with one deque for the maximum and one for the minimum, and is developed in monotonic stack and queue.

Which template for which question

Pitfalls that cost offers

• Negative numbers break any sum-based window. Check the sign constraint in the prompt before writing a line.
• Substring or subarray, not subsequence. A window is contiguous. If the characters may be skipped, it is a different problem.
• Forgetting to delete zero-count keys makes map.size lie, so the distinct-count rule never fires.
• if where while belongs. One removal may not restore validity.
• Off-by-one in the length. The length of [left, right] is right - left + 1. Writing right - left is the commonest slip, and it is wrong by exactly one on every answer.
• Recording at the wrong moment. Longest: after shrinking. Shortest: before removing. Counting: after shrinking.
• Re-initialising instead of sliding. Rebuilding the state for every window is the O(n · k) solution you were meant to replace.
• Empty input, k larger than the array, k = 0. Decide what each should return before you code, as with maxSumWindow above.

Recognizing it in an unseen problem

• The words "contiguous subarray" or "substring" (not subsequence)
• "Longest," "shortest," "maximum," or "minimum" over a contiguous range
• A brute force would check every [i, j] pair — O(n²) or worse
• The condition can be checked/updated incrementally as the window changes
• Adding an element can only push the window toward invalid, and removing one can only push it back (monotone validity); check this before the sign of the numbers
• "How many subarrays" with an "at most" rule, or "exactly K" that can be rewritten as at most K minus at most K − 1
• "Contains all the characters of T", "is a permutation of", or "at most K replacements/flips" over a string or a binary array
• "Maximum or minimum of every window of size k", which needs a monotonic deque rather than a running number