The Sliding Window Technique

Here’s a seemingly simple problem that has nothing to do with substring search. Say we have the array [3, 2, 7, 4, 6, 3, 5, 8], and we want to find the greatest contiguous four integers that yield the greatest sum when added together. Here’s what I mean.

The first four integers of the array 3, 2, 7, 4 are contiguous, meaning they’re all in a row. And when we add them together, we get a sum of 16. Cool.

The problem I’m proposing is to find the set of four contiguous integers that will yield the greatest sum in the array. For example, there’s another set of four contiguous numbers—7, 4, 6, 3—that add up to 20. Is this the greatest sum we can get, though? Let’s devise an algorithm to figure this out.

One approach we can take is brute force. Specifically, we simply try out every set of four contiguous numbers and keep track of which set gives us the greatest sum. That is, we try 3, 2, 7, 4 and then 2, 7, 4, 6 and then 7, 4, 6, 3, and so on.

To articulate the time complexity of this approach, we need to note that we have two variables to contend with. First, we have the length of the array, which we’ll call N. But we also have the number of how many contiguous integers we’re summing up. In our example, we’re working with sets of 4 contiguous numbers, but alternative problems might have us find the greatest sum of 3 numbers or 5 numbers. We’ll call this second variable K.

It turns out that for the brute-force approach, for each of the N elements of the array, we have to compute the sum of K elements. The only saving grace is that we don’t need to do this for the last three elements. Once we calculate the sum of the final four elements, we’re done—since there are no more groups of four elements after that point.

In the end, brute force here takes about NK steps, which in Big O is expressed as O(NK). This has the potential to get unwieldy if our problem involved more numbers. If, for example, our array had 1,000 values and we were adding up 10 contiguous numbers, we’d have to perform 10,000 steps. However, we can use a more clever approach—the *sliding window technique—to complete our task in O(N) time. Here’s how it goes.

We begin by computing the sum of the first four integers:

The box surrounding the four integers is our “window.” So far, we haven’t done anything clever. But watch what we do in the next step:

Instead of performing a brand-new computation to add up the next four integers, 2, 7, 4, 6, we only perform one subtraction and one addition. That is, because we know that the current window shares the numbers 7, 4, 6 with the previous window, we don’t need to add those numbers up again. The only difference between the current window and the old window is that the current window drops the 3 and adds an additional 6. So, to compute the sum of the current window, we take the sum of the old window, and simply subtract 3 and add 6.

This is the essence of the sliding window technique. Because the window “slides” incrementally, we only need to compute the differences between the new window and the old window instead of recomputing everything over again.

Moving on with our walkthrough, the 19 yielded by the current window is greater than the 16 produced by the previous window. (We can use a variable to keep track of the greatest sum we’ve encountered so far.) Let’s see what happens when we “slide the window” in the next step as shown in the .

Here, we subtract 2 and add 3, giving us 20, which is the greatest sum encountered so far. Although you may grasp the idea by now, let’s see this example to the end (even at the risk of you thinking me a flibbertigibbet).

We slide the window again:

This window yields 18. As of this point, 20 is still the greatest sum. We have one final step:

Aha! This final window sums to 22. Given that this is the greatest sum we’ve found, this is the result that our algorithm will output.

The efficiency of this approach is O(N) since we make a single pass through all N values. For each window, we perform a constant number of computations, that is, one addition and one subtraction. Even if the problem was changed so that we were searching for the greatest sum of 10—or even 100—contiguous numbers, this doesn’t affect the speed of our algorithm whatsoever. No matter what, we’ll only perform one addition and one subtraction for each of the N values. The K variable no longer matters.

This is a massive win since the sliding window algorithm executes in O(N) time vs. the O(NK) time of the brute-force approach.

Code Implementation: The Sliding Window Technique

Here is a Python implementation of the sliding window algorithm:

We begin by creating the initial window and storing the sum in the variable current_window_sum. We also create a variable max_sum_so_far, which will track the greatest window sum we encounter. We return this variable at the end of the function. To start, though, this variable will contain the sum of the current window.

We then begin a loop that “slides” the window along. We do this by starting the loop’s index (i) at 4. This is because array[4] is the value just to the right of the previous window. Because this is the new value we’re adding to the new window, we add this value (array[i]) to current_window_sum.

At the same time, we subtract from current_window_sum the value at array[i - 4], as this is the first value of the previous window. If the current_window_sum is greater than the max_sum_so_far, we update the max_sum_so_far to now be the current_window_sum. We then continue to slide the window by incrementing i, and repeat this entire process until we reach the end of the input array.

We’re now ready for the Rabin-Karp algorithm, which, in fact, uses the sliding window technique.