Sliding Window Technique

Programming isn't just about writing something that works, it is about finding the best solution with finite resources. To find the best, or even a good enough solution, you don't need to reinvent the wheel. Often times the solution you are looking for can be solved by an existing algorithm. Now I am not saying you should memorize all algorithms – that would be impossible. Instead, you should learn techniques that lead the way to common algorithmic solutions.

Hence, the sliding window technique. Before we get into it, I want you to imagine you are standing in front of the paned glass window in the picture above. Now imagine if I asked you to pick all of the squares that have a tree in them. You would look at each of the panes and see if you could find any trees. If one had a tree, you would mentally mark that down and keep looking.

This is almost exactly what the sliding window technique is. You use this strategy to break a larger picture (or set) and break it into smaller pieces (subsets) to see if they have what you are looking for. This allows us to search through sets of information in a much more efficient manner.

More specifically, the sliding window technique is a strategy for finding a solution in a sequence of characters, letters, or strings. Instead of performing many searches within the larger subset (brute-force approach), we can use a window to narrow our vision.

Essentially this allows us to turn two loops into one loop. This generally causes an improvement from O(n²) to O(n). At just 1000 elements this is the difference between 1,000,000 and 1000 operations.

Not all sliding window problems were created equal. Depending on what exactly you are looking for you will be able to accomplish this with a fixed-sized window, a dynamically resizable window, or either with the addition of an auxiliary data structure.

There are two things main giveaways that indicate that you should be using this technique.

1. There is a sequential set of elements (mainly strings, arrays, & LL)
2. The question is framed using the following keywords
   • min, max, longest, shortest, contained, subset, continuous, best

Now, let's get into the nitty-gritty with some examples.

Example 1 (fixed size window)

Let's say you are given a set of numbers:

6, 3, 7, 2, 4, 9

You are asked to find the largest sum of 3 continuous numbers in the list. If we employed the naive approach we would evaluate all the permutations of 3 contiguous numbers, choosing the max:

6 + 3 + 7 = 16

3 + 6 + 7 = 16, 3 + 7 + 2 = 12

7 + 6 + 3 = 16, 7 + 3 + 2 = 12, 7 + 2 + 4 = 13

2 + 3 + 7 = 12, 2 + 7 + 4 = 13, 2 + 4 + 9 = 15

4 + 7 + 2 = 13, 4 + 2 + 9 = 15

9 + 2 + 4 = 15

You would successfully tell me that 16 is the largest sum. Now, what's the problem with this? Well, first you are looking at every single permutation of size 3 in a list – unnecessarily duplicating your efforts. As you can see we counted with 7 nine times.

As a result, our run time would be O(n + m) where we have traversed the list n times and m is the number of groups of 3 we will need to evaluate. Space complexity is still just O(1) since we were able to accomplish this without creating another list.

A better way to solve this would be to take our window of size three and position it over the top of the numbers like this:

[6, 3, 7], 2, 4, 9 | sum = 16, maxSum = 16

When we shift the window to the right we aren't going to calculate 3 + 7 + 2. Instead, we are going to take sum - 6 + 2 and compare it to maxSum. If it is larger than the previous maxSum we will set maxSum = sum. We repeat until our window has reached the end.

6, [3, 7, 2], 4, 9 | sum = 12, maxSum = 16

6, 3, [7, 2, 4], 9 | sum = 13, maxSum = 16

6, 3, 7, [2, 4, 9] | sum = 15, maxSum = 16

Essentially what we have done is looked at each of the windows and asked ourselves, "Is this the best I can do?" Once we have reached the end we know that the maximum sum of three numbers in this list is 16, and we have done so in O(n) time. We also have a space complexity of O(1) since we did not need to add any other data structures other than miscellaneous counters.

Example 2 (fixed size window with a secondary data structure)

Now suppose we are asked to find all of all anagrams of p that are contained in s where:

s = "cbaebabacd", p = "abc"

We can identify this prompt as a sliding window question because it is asking us if something is contained within another set. We also know that this is a fixed size window as it asks us to find a match of a specific length.

To solve this problem we can break it down into a few steps:

1. First, we need to count how many of each letter there is in p and store it in an auxiliary data structure. This could be a hash table or an array. This data structure keeps track of the frequency of the letters in p.
2. Second, we put a window of size 3 on the top of s, so that our first iteration looks like this:
   [cba]ebabacd
3. Third, we evaluate if the frequency of letters in our window matches the frequency of letters in p. If it does we mark that down.
4. Finally, we keep shifting the window until we reach the end. Our final window will look like this:
   cbaebab[acd]

We would have found exactly two matches in this string cba and bac. Due to the fact that at worst p could be the length of s we have a space complexity of O(n).

Example 3 (dynamically sized window with a secondary data structure)

Finally, you are asked to find the longest substring in a string s, without repeating a character where:

s = "abcabcbb"

We can quickly pick this out as a sliding window problem because of the keywords:  longest and substring in a string. Notice how there is nothing indicating a specific size like the others? This tells us we have a dynamically sized window. We also know that we will need to use an auxiliary data structure to keep track of how many of each letter we have in each window.

1. First, we need to create an auxiliary data structure. This could be a hash table or an array. This data structure keeps track of the frequency of the letters in our window.
2. Second, we put a window of size 1 on the top of s, so that our first iteration looks like this:
   [a]bcabcbb
3. Third, we add this letter to our data structure and ask ourselves, "Is this the best I can do?". If we are not at the end or if we think we can do better, we grow the window like this:
   [ab]cabcbb
   • Every time we check to see if a letter has not been repeated and if not continue to grow. If a letter has been repeated we shrink the window from the left until we are back to only one of each letter:
     [abca]bcbb | two a's!
     a[bca]bcbb
4. Finally, we keep shifting the window until we reach the end. Our final window will look like this:
   abcabcb[b]

Using this approach we will have found the answer of 3 while maintaining a time complexity of O(n)! For the same reasons as for example 2, we will have a space complexity of O(n).