Sliding Window Pattern

The Sliding Window pattern is used to reduce the complexity of problems involving arrays or strings from O(N^2) to O(N). Instead of recalculating everything for every subarray, you "Slide" a window and only update the changes at the edges.

1. Fixed Window

Example: "Find the maximum sum of any contiguous subarray of size K." Instead of summing K elements for every index, you subtract the element that goes out of the window and add the new element that comes in.

2. Variable Window (Dynamic)

Example: "Find the smallest subarray with a sum greater than X." Here, the window grows until the condition is met, and then shrinks from the left to find the minimum size. This is the foundation of network **congestion control** algorithms.

int windowSum = 0;
for (int i = 0; i < array.Length; i++) {
    windowSum += array[i]; // Expand
    if (i >= k - 1) {
        maxSum = Math.Max(maxSum, windowSum);
        windowSum -= array[i - (k - 1)]; // Shrink from left
    }
}

4. Interview Mastery

Q: "How do you know when to use Sliding Window?"

Architect Answer: "You look for three keywords in the problem description: **Contiguous**, **Subarray/Substring**, and a **Max/Min/Target** value. If the problem asks for something related to a sequential range of data, Sliding Window is almost always the O(N) solution."