Sliding Window Explained

The sliding window technique reduces O(n²) nested loop problems to O(n) by maintaining a window over the data and sliding it incrementally. It is the go-to pattern for substring, subarray, and consecutive element problems.

Fixed-Size Window

The window size k is given. Slide a window of size k across the array and compute a result for each window position.

// Maximum sum subarray of size k
function maxSumSubarray(nums: number[], k: number): number {
  let windowSum = 0;
  // First window
  for (let i = 0; i < k; i++) windowSum += nums[i];
  let maxSum = windowSum;
  // Slide window
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}
// Time: O(n), Space: O(1)

Variable-Size Window

The window size changes based on a condition. Expand the window until the condition is violated, then shrink it until the condition is satisfied again.

// Longest substring without repeating characters
function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0, maxLen = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}
// Time: O(n), Space: O(min(n, alphabet size))

graph TD
    Init["Initialize: left=0, right=0, windowSum=0"]
    Expand["Expand: add arr[right] to windowSum"]
    Check{"right - left + 1 == k?"}
    Update["Update maxSum if windowSum > maxSum"]
    Shrink["Subtract arr[left] from windowSum\nleft++"]
    Move["right++"]
    Done["Return maxSum"]

    Init --> Expand
    Expand --> Check
    Check -->|"No"| Move
    Move --> Expand
    Check -->|"Yes"| Update
    Update --> Shrink
    Shrink --> Move

    style Init fill:#D97A2B,stroke:#B86418,color:#fff
    style Check fill:#D97A2B,stroke:#B86418,color:#fff
    style Expand fill:#FAF6EE,stroke:#E8DFC8
    style Update fill:#D4EDDA,stroke:#28A745
    style Shrink fill:#FAF6EE,stroke:#E8DFC8
    style Move fill:#FAF6EE,stroke:#E8DFC8
    style Done fill:#FAF6EE,stroke:#E8DFC8

When to Use Sliding Window

• Problem involves a contiguous sequence (subarray, substring).
• You need to find the longest/shortest/maximum/minimum of something.
• The brute force is O(n²) or O(n³) with nested loops.
• The problem has a "window" constraint (e.g., at most k distinct characters).

Common Patterns

• Maximum/minimum sum of subarray of size k: Fixed window, track running sum.
• Longest substring with at most k distinct characters: Variable window, expand right, shrink left when distinct count exceeds k.
• Minimum window substring: Variable window, expand to include all required chars, shrink to minimize.
• Permutation in string: Fixed window of size s1.length, compare character frequencies.

Common Mistakes

• Not updating the window state correctly when sliding : when you remove an element from the left, update your frequency map, sum, or count.
• Confusing when to expand vs shrink : expand right to grow, shrink left to satisfy the condition.
• Forgetting to check after the loop : the last window position may be the answer.
• Using sliding window for non-contiguous problems : if the problem allows skipping elements, sliding window doesn't apply.
• Off-by-one on window size : the window includes both left and right indices. Size = right - left + 1.