Sliding Window Pattern

The sliding window pattern computes results over all contiguous sub-arrays of a given size (or satisfying a constraint) in O(n) by incrementally updating a running aggregate instead of restarting from scratch each time.

5 min read Level 2/5 #dsa#arrays#strings

What you'll learn

Implement a fixed-size sliding window for computing moving averages and maximums
Implement a dynamic sliding window for finding the longest substring without repeated characters
Explain how the window's shrink condition keeps the algorithm linear

A sliding window is a subarray (or substring) defined by two pointers left and right that both move to the right. As right expands the window, you include a new element in your aggregate. When the window violates a constraint, you advance left to shrink it. Because each element enters and leaves at most once, the total work is O(n).

Fixed-Size Window

When the window length k is constant, right advances one step at a time and left always trails by exactly k positions.

// Maximum sum of any contiguous subarray of length k
function maxSumFixed(nums, k) {
  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];        // include new element
    windowSum -= nums[right - k];   // drop element that left the window
    if (windowSum > maxSum) maxSum = windowSum;
  }
  return maxSum;
}

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

Dynamic Window

When the window size is not fixed, right expands greedily and left advances only when the window becomes invalid.

Longest Substring Without Repeating Characters

This is the canonical dynamic-window problem. The invariant is: every character in [left, right] is unique.

function lengthOfLongestSubstring(s) {
  const seen = new Map(); // char -> most recent index
  let left = 0;
  let 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 (seen.has(ch) && seen.get(ch) >= left) {
      left = seen.get(ch) + 1;
    }

    seen.set(ch, right);
    const windowLen = right - left + 1;
    if (windowLen > maxLen) maxLen = windowLen;
  }
  return maxLen;
}

// Walk-through: s = "abcabcbb"
// right=0 a → window "a"       maxLen=1
// right=1 b → window "ab"      maxLen=2
// right=2 c → window "abc"     maxLen=3
// right=3 a → left moves to 1, window "bca"  maxLen=3
// right=4 b → left moves to 2, window "cab"  maxLen=3
// right=5 c → left moves to 3, window "abc"  maxLen=3
// right=6 b → left moves to 5, window "cb"   maxLen=3
// right=7 b → left moves to 7, window "b"    maxLen=3
console.log(lengthOfLongestSubstring("abcabcbb")); // 3

Choosing the Right Variant

Variant	When to use	Time	Space
Fixed window	”subarray of size k”	O(n)	O(1)
Dynamic window (shrink on violation)	“longest/shortest satisfying constraint”	O(n)	O(k) for auxiliary map/set
Brute force (all subarrays)	Never in production	O(n²) or worse	O(1)

The key question is: when you add right, can you determine in O(1) whether the window is now invalid? If yes, a sliding window works.

Up Next

Prefix sums are another O(n) preprocessing trick — one that answers range-sum queries in O(1) instead of scanning the subarray each time.

Prefix Sums →