Sliding window: the linear-time answer to subarray questions

A large family of array problems asks some version of the same question: find the subarray that satisfies a condition, where the condition is about the subarray's contents. Longest subarray with sum ≤ k. Smallest subarray with sum ≥ k. Longest substring with at most k distinct characters.

These all have brute-force solutions that enumerate every subarray in O(n²). They all have O(n) solutions using the sliding window.

#The mental model

A sliding window is a range [left, right] that you expand and shrink as you scan the array. The invariant: the current window always satisfies (or nearly satisfies) the condition. When expanding the window breaks the condition, you shrink from the left until the condition holds again.

The reason this is O(n): each element is added to the window (when right advances) exactly once, and removed (when left advances) at most once. Total work: 2n moves.

#Fixed-size window: maximum sum of k elements

The simplest case. The window size is given; you slide it without changing its size.

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

Each slide: add the element entering from the right, subtract the element leaving from the left. One operation per step, no nested loops.

#Variable-size window: longest subarray with sum ≤ k

When the window size is not fixed, a left pointer chases right:

function longestSubarrayWithSum(nums: number[], k: number): number {
  let left = 0;
  let sum = 0;
  let maxLen = 0;
 
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right]; // expand window
 
    while (sum > k) {  // shrink until condition holds
      sum -= nums[left];
      left++;
    }
 
    maxLen = Math.max(maxLen, right - left + 1);
  }
 
  return maxLen;
}

The while loop looks like it could push this to O(n²), but it does not. left only ever moves forward and never overtakes right. Total advances of left across the entire run: at most n.

#Variable-size with a frequency map: longest substring with k distinct characters

When the condition is structural rather than arithmetic, maintain a frequency map alongside the window:

function longestKDistinct(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxLen = 0;
 
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    freq.set(c, (freq.get(c) ?? 0) + 1);
 
    while (freq.size > k) {
      const lc = s[left];
      freq.set(lc, freq.get(lc)! - 1);
      if (freq.get(lc) === 0) freq.delete(lc);
      left++;
    }
 
    maxLen = Math.max(maxLen, right - left + 1);
  }
 
  return maxLen;
}

The window expands by adding characters. When the distinct count exceeds k, it shrinks until the count is back to k. Deleting a key when its count hits zero keeps freq.size accurate as the window moves.

#Minimum window substring (hardest variant)

Sometimes you need the smallest window satisfying a condition. The pattern flips: expand until valid, record the result, then shrink to see if something smaller also works.

function minWindow(s: string, t: string): string {
  const need = new Map<string, number>();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
 
  const have = new Map<string, number>();
  let formed = 0;
  const required = need.size;
  let left = 0, minLen = Infinity, minStart = 0;
 
  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    have.set(c, (have.get(c) ?? 0) + 1);
    if (need.has(c) && have.get(c) === need.get(c)) formed++;
 
    while (formed === required) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        minStart = left;
      }
      const lc = s[left];
      have.set(lc, have.get(lc)! - 1);
      if (need.has(lc) && have.get(lc)! < need.get(lc)!) formed--;
      left++;
    }
  }
 
  return minLen === Infinity ? '' : s.slice(minStart, minStart + minLen);
}

The formed/required counters track whether the current window satisfies the condition without iterating the full map on every step. This is the same expand-then-shrink structure — the only difference is that we shrink while the condition holds and record results inside the shrink loop.

#Recognizing sliding window problems

The pattern applies when:

• You are asked about a contiguous subarray or substring
• The condition on the window is monotone: a larger window is always harder (or always easier) to satisfy, never unpredictably different
• The brute force checks every pair of (left, right) indices

The monotone property is what makes the left pointer safe to advance without backtracking. For sum conditions, a larger window always has a larger sum. For distinct-character conditions, a larger window has at least as many distinct characters. These guarantee that if the condition is violated, shrinking from the left can only help.

The window is a bet: if the current range violates the condition, expanding it makes things worse, so we shrink. The monotone property is what makes that bet valid.

Sliding window is not a trick you memorize per-problem. It is a strategy: maintain a range, expand greedily, shrink when the invariant breaks, record results when it holds. Once the structure is clear, the code mostly writes itself.