Introduction to Sliding Window
Let’s go over the Sliding Window pattern, its real-world applications, and some problems we can solve with it.
We'll cover the following...
About the pattern
Imagine you have a tray of 10 cookies and want to find the most chocolate chips in any 3 cookies next to each other. You must count the chips in every possible group of 3 cookies to do this. It might seem easy with just 10 cookies, but imagine doing the same when there are thousands or more. This can become time-consuming. We can avoid this hassle by using a smarter approach. Instead of recounting the chips for each group from scratch, you start by counting the chips in the first 3 cookies. Then, as you move to the next group, you simply subtract the chips from the cookie you leave behind and add the chips from the new cookie you include. This way, you quickly check each group without starting over every time. This smart technique is called the sliding window pattern.
The sliding window pattern is a technique for efficiently processing sequential data, such as arrays and strings. It involves maintaining a dynamic window that slides across the data, allowing you to examine a fixed portion at a time. Instead of repeatedly scanning the entire dataset, this approach adjusts the window’s boundaries as needed to track relevant elements. It is especially useful for solving problems involving contiguous subarrays or substrings, such as finding the maximum sum of a subarray or detecting repeated patterns in a string. This pattern can be viewed as a variation of the two-pointer approach, where the pointers define the window’s start and end.
Depending on the problem, the sliding window can be of a fixed size or dynamic.
The fixed-size window is used when the window size is given or constant. For example, find the largest sum of any three consecutive numbers.
The dynamic window is used when the window size changes based on conditions. For example, find the smallest subarray whose sum exceeds a target. ...