Introduction to Sliding Window

About the pattern

The sliding window pattern is used to process sequential data, arrays, and strings, for example, to efficiently solve subarray or substring problems. It involves maintaining a dynamic window that slides through the array or string, adjusting its boundaries as needed to track relevant elements or characters. The window is used to slide over the data in chunks corresponding to the window size, and this can be set according to the problem’s requirements. It may be viewed as a variation of the two pointers pattern, with the pointers being used to set the window bounds.

Imagine you’re in a long hallway lined with paintings, and you’re looking through a narrow frame that only reveals a portion of this hallway at any time. As you move the frame along the hallway, new paintings come into view while others leave the frame. This process of moving and adjusting what’s visible through the frame is akin to how the sliding window technique operates over data.

Why is this method more efficient? Consider we need to find $k$ consecutive integers with the largest sum in an array. The time complexity of the naive solution to this problem would be $O(kn)$ , because we need to compute sums of all subarrays of size $k$. On the other hand, if we employ the sliding window pattern, instead of computing the sum of all elements in the window, we can just subtract the element exiting the window, add the element entering the window, and update the maximum sum accordingly. In this way, we can update the sums in constant time, yielding an overall time complexity of $O(n)$. To summarize, generally, the computations performed every time the window moves should take $O(1)$ time or a slow-growing function, such as the log of a small variable.

Here is the template for sliding window, where we maintain a dynamic window that adjusts as we traverse the array.