Nanda Syahrasyad

Last updated March 2, 2021

After multiple failed coding assessment tests last summer, I enrolled in the Grokking the Coding Interview course. The course was different from other data structures and algorithms courses because it focused on common algorithmic patterns. The main idea behind the patterns is this: if you're able to frame a coding problem to match one of the patterns, you're well on your way to reaching an optimal solution.

While the course itself is incredibly informative, I felt that visualizing the patterns themselves makes them just a bit more clear to understand.

In this post, I talk about the first pattern that they cover — the sliding window pattern. We'll first walk through a problem without the pattern, then we'll try to iteratively improve our solution, revealing the final pattern in the end.

An Addicted Data Scientist

Let's pretend that I'm a data scientist that absolutely loves chocolate. As a data scientist, I naturally keep track of the number of chocolates that I eat on a daily basis. One day I wondered — how many chocolates do I eat on average over any consecutive 3 day period? (an every-day question to ask, of course).

I could do this by hand, but I'm lazy. I also want it to work with any period of consecutive days and with any number of data points I may have. So I decide to write an algorithm to answer this question for me.

The algorithm takes in two parameters — a list of data points chocolates, where each number represents the number of chocolates I ate on a given day, and a number period that represents the period of consecutive days I want to take the average from. The algorithm should output another list of numbers, where each number represents the average number of chocolates eaten over a consecutive period number of days.

averageChocolatesEaten(chocolates: number[], period: number): number[]

For example, if we give the algorithm the list [1, 2, 3, 4] and the period 3, the algorithm's going to return the list [2, 3]. [1, 2, 3, 4] breaks down into two 3-day periods, [1, 2, 3], and [2, 3, 4], with an average of 2 and 3 respectively.

How do we design the algorithm?

First Approach

My first approach to this would be to follow the steps logically:

1. Break down the list of numbers to sublists with length period each
2. Take the average of each sublist
3. Put the averages together

To build the sublists, we repeatedly take period elements from the list until we hit the end of the list:

Since we're already going through each sublist one at a time, we may as well count the sum (and subsequently, the average) as we go. Once we've done that, we have the completed algorithm:

That was easy! We’re not quite done yet though. We can do better.

On the top right of the animation box you’ll see a number. This number represents the total number of steps the algorithm needs to do to compute its result. Given the list of numbers [1,2,3,4] for example, the algorithm needs 7 steps to get to the final result.

Let's see what happens to the number of steps when we change the size of the inputs. In the box below, I doubled the size of the data to 8 numbers:

Notice the number on the top right again — it jumped up to 19 steps! It makes sense for the number to go up, but maybe there's a way so that it doesn't go up as much as it did.

A Window of Opportunity

Here's the algorithm again. Do you see anything that seems wasteful or unnecessary? Here's a hint — try to see what happens when we transition from one sublist to the next.

Let's look at that transition step one more time:

When we move from one sublist to the next, we are (quite literally) dropping elements that we have already counted, only to count it again in the next iteration.

This effect is especially pronounced when the size of period is close to the size of the list of chocolates:

It turns out that no matter what inputs you give the algorithm, this approach will always double count every element except for the first and the last (try playing around with the inputs to convince yourself!)

So why are we double counting in the first place? If we look at the first two sublists, we see that there's a lot of similarity between the two lists:

By starting over every time we reach a new element, we don't take advantage of this similarity. If we're somehow able to calculate the average for both sublists without double counting, we would be able to cut down on a lot of needless steps.

As a matter of fact, there's a way to do exactly that!

Notice that for the example above, the sum of the second sublist is equal to the sum of the first sublist minus one and plus four:

Generally speaking, the sum of the second sublist is the sum of the first sublist, minus the first element of the first sublist, plus the last element of the second sublist. Using this formula, we can derive the sum of the next sublist from the current one, ultimately avoiding the need to recount everything all over again. By doing this, we reduce the number of steps needed to count the sum from period steps to only one step!

If we do the subtraction and addition in one step, it's as if we're sliding a window (see where I'm getting at here?) of elements from one sublist to the next:

Rewriting the Algorithm

With this key insight let's rewrite the algorithm. Remember that the algorithm receives two inputs - a list of numbers chocolates and the period of consecutive days period.

The sliding window trick only takes into effect when we transition from one sublist to the next. At the start, we don't even have a sublist, so we have to build the sublist as we did before — by iterating through the first period elements.

Then, we use our sliding window trick to slide to the next sublist. Again, what we're really doing here is subtracting the first element of the original sublist and adding the last element of the next sublist. We use this sum to calculate the average of the list and add that average to the final result.

Finally, we keep sliding until we hit the end of the chocolates list.

Putting all three steps together, we get the final algorithm:

And there you have it — the sliding window pattern!

Based on these examples alone, we see that this new version does seem faster — the original algorithm takes 7 steps for a 4-length input, while the sliding window algorithm takes the same amount of steps for a 6-length input.

This doesn't seem like a fair comparison though, so let's do a test. How would the two algorithms compare when we give it the exact same inputs?

While the window is building, both algorithms are going at the same pace (try changing the size of period to the size of the list — both algorithms will finish at the same time!). However, once the window is complete, the optimal algorithm blazes off and terminates in less than half the time it takes for the old algorithm to finish.

Generalizing the Pattern

A pattern wouldn't be much of a pattern if it works for only one use case. What makes the sliding window pattern a pattern is that it secretly hides in a bunch of other similar problems — typically those that involve sublists, subarrays, or substrings. The chocolates problem is just one costume the sliding window pattern puts on.

Generally speaking, the pattern needs:

1. A window, i.e. a fixed range of elements
2. A state to maintain in that window
3. A way to derive the next state using only the current state and the stuff that enters or leaves the window

"Only" is the keyword here — if we need to go through the entire window again, the pattern wouldn't be any faster than the way we were doing it before.

The chocolates problem that we were working through meets all of this criteria:

1. A window — the consecutive period of days
2. A state to maintain in that window — the total sum of the numbers in the period of days
3. A way to derive the next state solely by the stuff that enters or leaves the window — to get the next sum, take the current sum, subtract the number that leaves the window and add the number that enters the window

To end it off, let's look at one more problem that, unfortunately, has nothing to do with chocolates.

Permutation in a String

Given a string and some pattern, determine if the string contains any permutation of that pattern.

For example, given the string aaacb and the pattern abc, the algorithm should return true because aaacb contains acb, which is a permutation of abc.

Before I show you the solution, see if you can frame this problem to fit the sliding window pattern in. Try to use the criteria that we've defined in the previous section.

Done? Awesome. A bit stuck? No worries. We'll go through the criteria one-by-one to see if we can use the sliding window pattern to solve this problem.

1. The window

Figuring out what the window would be is a bit tricky because the problem doesn't explicitly tell you what the size of the substring is.

If we look back at the definition of a permutation though, we can conclude that two strings of different sizes can never be permutations of one another! After all, the longer string will always have more characters than the other, so you can never rearrange it to create a shorter string.

Since we're trying to match substrings with the pattern, we can conclude that the window is the substring of length pattern.length.

2. A state to maintain in the window

One way to figure out what state to maintain is to trace back from the result you want — what information do I need to determine if the substring in this window is a permutation of the pattern?

A way to check if two strings are permutations of each other is to see if they have the exact same characters and the exact same number of those characters. We can do this by keeping track of the frequencies of each character for each string and comparing them on a per-character basis:

If everything matches, then we know that our strings are permutations of each other. If any one of the counts don't match, then we know that the strings cannot be permutations.

Great — this means the state we would have to maintain is the character frequency table of the current window.

3. A way to derive the next state solely by the stuff that enters or leaves the window

The simplest way to do this is to ignore it altogether! By recounting everything every time we try a different substring, we get an algorithm that works:

But of course you don't just want an algorithm that works, you want a fast algorithm that works. Let's think about the bottlenecks. Whenever we move from one substring to another, we have to do two things:

1. Calculate the frequency table for the new substring, and
2. compare this new frequency table with the pattern's table.

We can optimize (1) by simply adding the letter entering the window and subtracting the letter leaving the window; but how do we optimize (2)?

If you think about it, we don't actually care about the character counts of the substring — we only care if those counts match the one in the pattern. What if, instead of having to handle two tables, we handle only one table—the pattern's table—and make the updates on it instead?

Here's the plan: every time a letter enters the window, you subtract that letter's count in the pattern's frequency table. Whenever a letter leaves, you do the opposite—add back that letter's count in the pattern's frequency table. In a sense we're turning the pattern's frequency table to a table of the difference between the pattern and the current window. This means that when the count for the whole table is zero, the window is a permutation of the pattern.

Finally, everything put together:

Summary

Overall, the sliding window pattern is a cool way to think about problems involving subcollections by optimizing the way you move from one candidate to the next. There's more we can talk about here (e.g. what happens if the different sublists are not the same size?) but this post is long enough as is so we'll leave it for next time :)

Thanks for reading!