Sign in to track progress and bookmarks.
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."
Quizzes linked to this course—pass to earn certificates.
On this page
1. Fixed Window 2. Variable Window (Dynamic) 4. Interview Mastery