Sliding Window

The sliding window pattern converts O(n²) or O(n³) brute-force solutions for subarray/substring problems into O(n) by maintaining a window that slides across the input rather than recomputing from scratch at every position.

Two flavours:

Fixed-size window — the window is always exactly k elements wide.
Variable-size window — the window grows and shrinks to satisfy a constraint.

Fixed-Size Window — Maximum Sum Subarray of Size k

Problem: given an array of integers and a number k, find the maximum sum of any contiguous subarray of length exactly k.

Brute force recomputes the sum for each of the n−k+1 windows → O(n·k). Sliding window maintains a running sum, subtracting the leftmost element and adding the new rightmost element as the window advances → O(n).

function maxSumSubarray(nums, k) {
  let windowSum = 0;

  // Build the first window
  for (let i = 0; i < k; i++) windowSum += nums[i];

  let maxSum = windowSum;

  // Slide: add right element, remove left element
  for (let right = k; right < nums.length; right++) {
    windowSum += nums[right] - nums[right - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

console.log(maxSumSubarray([2,1,5,1,3,2], 3)); // 9  (5+1+3)
console.log(maxSumSubarray([2,3,4,1,5],   2)); // 7  (3+4)

Note

Fixed window: the right pointer moves right once per iteration. The left pointer is always right - k. Time: O(n). Space: O(1).

Variable-Size Window — Template

Variable windows solve problems of the form: "find the longest/shortest subarray that satisfies some constraint".

The pattern is: expand the right boundary unconditionally; shrink the left boundary whenever the constraint is violated.

// Generic variable-size sliding window template
function variableWindow(arr) {
  let left = 0;
  let result = 0;       // or Infinity for "minimum" problems
  let windowState = {}; // whatever state tracks the constraint

  for (let right = 0; right < arr.length; right++) {
    // 1. Expand: add arr[right] to the window
    // update windowState with arr[right]

    // 2. Shrink: while the window violates the constraint, move left
    while (/* constraint violated */) {
      // remove arr[left] from windowState
      left++;
    }

    // 3. Update result — window [left, right] now satisfies constraint
    result = Math.max(result, right - left + 1);
  }
  return result;
}

Problem 1 — Longest Substring Without Repeating Characters

LeetCode 3. Find the length of the longest substring with all unique characters.

Constraint to maintain: no character appears more than once in the window.

function lengthOfLongestSubstring(s) {
  const lastSeen = new Map(); // char → most recent index
  let left = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // If ch was seen inside the current window, shrink from the left
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) {
      left = lastSeen.get(ch) + 1;
    }
    lastSeen.set(ch, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

console.log(lengthOfLongestSubstring('abcabcbb')); // 3 ('abc')
console.log(lengthOfLongestSubstring('bbbbb'));    // 1 ('b')
console.log(lengthOfLongestSubstring('pwwkew'));   // 3 ('wke')

Tip

Storing the last-seen index instead of using a Set lets you jump the left pointer forward in O(1) rather than shrinking one step at a time.

Problem 2 — Minimum Size Subarray Sum

LeetCode 209. Find the smallest contiguous subarray whose sum ≥ target. Return 0 if no such subarray exists.

function minSubArrayLen(target, nums) {
  let left = 0, windowSum = 0, minLen = Infinity;

  for (let right = 0; right < nums.length; right++) {
    windowSum += nums[right];

    // Shrink from left while the condition is satisfied
    while (windowSum >= target) {
      minLen = Math.min(minLen, right - left + 1);
      windowSum -= nums[left];
      left++;
    }
  }
  return minLen === Infinity ? 0 : minLen;
}

console.log(minSubArrayLen(7, [2,3,1,2,4,3])); // 2  ([4,3])
console.log(minSubArrayLen(4, [1,4,4]));        // 1  ([4])
console.log(minSubArrayLen(11, [1,1,1,1,1,1])); // 0

Problem 3 — Longest Substring with At Most K Distinct Characters

LeetCode 340. Find the longest substring containing at most k different characters.

function lengthOfLongestSubstringKDistinct(s, k) {
  const freq = new Map();
  let left = 0, maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    freq.set(ch, (freq.get(ch) ?? 0) + 1);

    // More than k distinct chars — shrink window
    while (freq.size > k) {
      const leftCh = s[left];
      freq.set(leftCh, freq.get(leftCh) - 1);
      if (freq.get(leftCh) === 0) freq.delete(leftCh);
      left++;
    }
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

console.log(lengthOfLongestSubstringKDistinct('eceba', 2)); // 3 ('ece')
console.log(lengthOfLongestSubstringKDistinct('aa', 1));    // 2

Problem 4 — Fruit Into Baskets

LeetCode 904. You have two baskets (k = 2), each holding one fruit type. Pick the maximum number of fruits from a contiguous subarray using at most 2 distinct fruit types.

This is exactly "Longest Substring with At Most 2 Distinct Characters" with a different story.

function totalFruit(fruits) {
  const basket = new Map(); // fruit type → count in window
  let left = 0, maxPicked = 0;

  for (let right = 0; right < fruits.length; right++) {
    const f = fruits[right];
    basket.set(f, (basket.get(f) ?? 0) + 1);

    // More than 2 distinct fruits — remove from left
    while (basket.size > 2) {
      const lf = fruits[left];
      basket.set(lf, basket.get(lf) - 1);
      if (basket.get(lf) === 0) basket.delete(lf);
      left++;
    }
    maxPicked = Math.max(maxPicked, right - left + 1);
  }
  return maxPicked;
}

console.log(totalFruit([1,2,1]));       // 3
console.log(totalFruit([0,1,2,2]));     // 3  ([1,2,2])
console.log(totalFruit([1,2,3,2,2]));   // 4  ([2,3,2,2])

Note

Notice that Fruit Into Baskets and Longest Substring with K Distinct are the same problem. Pattern recognition — mapping a word problem to a known template — is the real interview skill.

When to Reach for Sliding Window

Signal in the problem	Window type
"subarray / substring of length k"	Fixed window
"longest subarray / substring that …"	Variable window (maximise)
"shortest / minimum subarray that …"	Variable window (minimise, shrink when valid)
"at most k", "no more than k"	Variable window with frequency Map
"exactly k" occurrences	atMost(k) - atMost(k-1) trick

Tip

The "exactly k" trick: count(exactly k) = count(at most k) - count(at most k-1). Write the at-most version once and call it twice.

Practice Problems

LeetCode 643 — Maximum Average Subarray I (fixed window)
LeetCode 3 — Longest Substring Without Repeating Characters
LeetCode 209 — Minimum Size Subarray Sum
LeetCode 340 — Longest Substring with At Most K Distinct Characters
LeetCode 904 — Fruit Into Baskets
LeetCode 76 — Minimum Window Substring (variable + character frequency)
LeetCode 567 — Permutation in String (fixed window + frequency match)
LeetCode 992 — Subarrays with K Different Integers (exactly-k trick)