Sliding Window Pattern

Why this pattern matters for LeetCode

The brute force tries every starting index and computes the result from scratch each time. That is O(n²) or worse. Sliding Window is O(n) because you never restart — you add what enters the window on the right and remove what leaves on the left. The state you track (a sum, a character count, a set of values) updates incrementally at each step. This pattern is the key to making subarray problems fast.

What the Sliding Window pattern is

A sliding window maintains a contiguous subarray and moves it across the input. Fixed-size windows move one step at a time and keep a constant width — add the new right element, remove the old left element, update the answer. Variable-size windows expand by moving the right pointer and shrink by moving the left pointer when a constraint is violated. The window always represents the best candidate you've found so far.

Reach for Sliding Window when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Sliding Window

• ✓Maximum or minimum sum of a subarray of fixed size k
• ✓Longest substring without repeating characters (variable window)
• ✓Shortest subarray whose sum is at least target (variable window, shrink when constraint is met)
• ✓Any problem that asks for the best contiguous range satisfying some property
• ✓Permutation or anagram detection inside a larger string (fixed window with frequency map)

When NOT to use Sliding Window

• ✕The elements you care about are not contiguous — use a hash map or Two Pointers
• ✕The window can't be computed incrementally (each new state requires knowing all elements) — may need a different approach
• ✕The problem involves pairs at specific positions rather than ranges — use Two Pointers
• ✕The constraint involves non-adjacent elements — sliding window won't apply directly

Better alternative: In those cases, Two Pointers (for value comparisons at positions) or a prefix sum array (for non-incremental range queries) may work better.

JavaScript code template

Variable-size sliding window — Longest Substring Without Repeating Characters

function lengthOfLongestSubstring(s) {
  const seen = new Map(); // char -> last index
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];

    // If char was seen inside the current window, shrink from the left
    if (seen.has(char) && seen.get(char) >= left) {
      left = seen.get(char) + 1;
    }

    seen.set(char, right);            // update last seen index
    maxLen = Math.max(maxLen, right - left + 1); // window size
  }

  return maxLen;
}

Right expands the window one character at a time. When a duplicate enters the window, left jumps past the previous occurrence to remove the duplicate. The window [left, right] always contains a valid substring with no repeating characters. Track the maximum window size seen across all valid windows.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Set left = 0 and initialize any state you need to track (sum, character count, map).
2. 2Loop right from 0 to n-1, expanding the window by adding s[right] to the tracked state.
3. 3After adding, check if the window violates the constraint.
4. 4While the constraint is violated, shrink from the left: remove s[left] from state, increment left.
5. 5The window is now valid — update the best answer (max length, max sum, etc.).
6. 6Return the best answer after the loop ends.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Maximum Average Subarray I

  Fixed window of size k — add the new element on the right, subtract the leaving element on the left, track the max sum.

  Premium→
• Longest Substring Without Repeating Characters

  Variable window — expand right, shrink left when a duplicate character enters the window.

  Premium→
• Minimum Size Subarray Sum

  Variable window — expand until sum >= target, then shrink from left as far as possible.

  Premium→
• Permutation in String

  Fixed window of size p.length — compare character frequency maps at each position.

  Premium→
• Fruit Into Baskets

  Variable window with at most 2 distinct types — shrink when a third type enters.

  Premium→

Common mistakes beginners make

• ✕Recomputing the window sum from scratch each step — that's the O(n×k) brute force you're trying to avoid.
• ✕Forgetting to shrink the window when the variable-window constraint is violated — causes infinite loops or wrong answers.
• ✕Off-by-one on when the window is first full: the condition is i >= k - 1, not i >= k.
• ✕Confusing Two Pointers with Sliding Window — Sliding Window tracks the aggregate state inside the range; Two Pointers compares values at two positions.

Sliding Window vs Two Pointers

Choose the right tool for the job.

Time and space complexity

Each element is added to the window once (right pointer) and removed from the window at most once (left pointer). Both pointers together make at most 2n moves — O(n) total. For fixed windows, you need only a running sum — O(1) space. For variable windows tracking character positions or counts, the map holds at most as many entries as the window size — O(k) space.

Frequently asked questions

What's the difference between a fixed and variable sliding window?

A fixed window always has the same size (k). You add one element on the right, remove one on the left, and check the answer. A variable window expands freely but shrinks when a constraint is violated. The right pointer always moves forward; the left pointer moves forward only when needed.

How do I know when to shrink the window?

Shrink when the current window violates the constraint. For Longest Substring Without Repeating Characters, the constraint is 'no duplicate characters' — shrink when a duplicate enters. For Minimum Size Subarray Sum, the constraint is 'sum >= target' — shrink when you've met the target to see if you can do it with fewer elements.

How is Sliding Window different from Two Pointers?

The terms overlap, but the key difference is what you track. Sliding Window maintains internal state about what's inside the window (a sum, a frequency map, a set). Two Pointers usually just compares values at the two pointer positions without caring about what's between them.

Why is Sliding Window O(n) and not O(n²)?

Because each element is added to the window exactly once (when right passes it) and removed at most once (when left passes it). Both pointers together make at most 2n moves. There's no restart from scratch — you update state incrementally.

Can Sliding Window work on 2D problems?

Sometimes, but it gets complicated. For 1D subarrays and substrings, Sliding Window is the go-to. For 2D matrices you often need a different approach — prefix sum matrices or treating each row as a compressed 1D problem.