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.
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.
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
}
}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."