What is Sliding Window Design Pattern algorithm?

What is Sliding Window Design Pattern algorithm?

If you are doing leetcode then you have definitely encountered problems related to array and subarray. You might have used some nested loops to solve this kind of problem. But what if you saw the same problem during your interview and your interviewer asked to solve it using one iteration.

In order to solve such kinds of problems, a sliding window design pattern was introduced.  The design pattern helps us to solve most of the problems in o(n) time efficiency. Once you start solving a couple of problems with the sliding window design pattern, you can easily find what are the problems that could be solved using it.

But the main question is how does the sliding window design pattern work? You can relate to this pattern with the sliding windows that are in your home. When you slide these windows, you are sliding both the ends.  But you cannot slide the window further once the end side reaches the end of the wall.

To simulate the sliding window, what we need is two pointers. We keep these two pointers at the start position and at the end position. We slide both the pointers at once unless the pointer at the last position reaches the end of an array.

Let us see how the sliding window design pattern will look like with an example.

The sliding window pattern that we saw above is also called a fixed-sized sliding windows pattern. However, there is also a dynamically resizable sliding window design pattern that you might need to use while solving different algorithmic questions. In a dynamically resizable sliding window pattern, the gap between the start pointer and end pointer may shrink or expand while they move forward. Let me show how it will look like with the above example.

Nevertheless, we will look at a lot of problems that can be solved using fixed-size sliding windows and dynamically resizable sliding window design patterns. Solving these problems will definitely help us to learn and understand more about these patterns.