What is Sliding Window Algorithm? Examples?

Question

While solving a geometry problem, I came across an approach called Sliding Window Algorithm.

Couldn't really find any study material/details on it.

What is the algorithm about?

Solution 1

Generally speaking a sliding window is a sub-list that runs over an underlying collection. I.e., if you have an array like

[a b c d e f g h]

a sliding window of size 3 would run over it like

[a b c]
  [b c d]
    [c d e]
      [d e f]
        [e f g]
          [f g h]

This is useful if you for instance want to compute a running average, or if you want to create a set of all adjacent pairs etc.

Solution 2

I think of it as more a technique than an algorithm. It's a technique that could be utilized in various algorithms.

I think the technique is best understood with the following example. Imagine we have this array:

[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]

How would we find the largest sum of five consecutive elements? Well, we'd first look at 5, 7, 1, 4, 3 and see that the sum is 20. Then we'd look at the next set of five consecutive elements, which is 7, 1, 4, 3, 6. The sum of those is 21. This is more than our previous sum, so 7, 1, 4, 3, 6 is currently the best we've got so far.

Let's see if we could improve. 1, 4, 3, 6, 2? No, that sums to 16. 4, 3, 6, 2, 9? That sums to 24, so now that's the best sequence we've got. Now we move along to the next sequence, 3, 6, 2, 9, 2. That one sums to 22, which doesn't beat our current best of 24. And we've reached the end, so we're done.

The brute force approach to implementing this programmatically is as follows:

const getMaxSumOfFiveContiguousElements = (arr) => {
  let maxSum = -Infinity;
  let currSum;

  for (let i = 0; i <= arr.length - 5; i++) {
    currSum = 0;

    for (let j = i; j < i + 5; j++) {
      currSum += arr[j];
    }

    maxSum = Math.max(maxSum, currSum);
  }

  return maxSum;
};

What is the time complexity of this? It's O(n*k). The outer loop is going through n - k + 1 items, but when n is much larger than k, we can forget about the k + 1 part and just call it n items. Then the inner loop is going through k items, so we have O(n*k). Try visualizing it like this:

Can we get this down to just O(n)? Let's return to this array:

[ 5, 7, 1, 4, 3, 6, 2, 9, 2 ]

First we get the sum of 5, 7, 1, 4, 3. Next we need the sum of 7, 1, 4, 3, 6. Visualize it like this, with a "window" surrounding each group of five elements.

What's the difference between the first window and the second window? Well, the second window got rid of the 5 on the left but added a 6 on the right. So since we know the sum of the first window was 20, to get the sum of the second window, we take that 20, subtract out the 5, and add the 6 to get 21. We don't actually have to go through each element in the second window and add them up (7 + 1 + 4 + 3 + 6). That would involve doing repeated and unnecessary work.

Here the sliding window approach ends up being two operations instead of five, since k is 5. That's not a huge improvement, but you can imagine that for larger k (and larger n) it really does help.

Here's how the code would work using the sliding window technique:

const getLargestSumOfFiveConsecutiveElements = (arr) => {
  let currSum = getSum(arr, 0, 4);
  let largestSum = currSum;

  for (let i = 1; i <= arr.length - 5; i++) {
    currSum -= arr[i - 1]; // subtract element to the left of curr window
    currSum += arr[i + 4]; // add last element in curr window
    largestSum = Math.max(largestSum, currSum);
  }

  return largestSum;
};

const getSum = (arr, start, end) => {
  let sum = 0;

  for (let i = start; i <= end; i++) {
    sum += arr[i];
  }

  return sum;
};

And that's the gist of the sliding window technique. In other problems you may be doing something more complicated than getting the sum of the elements inside the window. Or the window itself may be of varying size instead of the fixed size of five that we saw here. But this basic application of the sliding window technique should give you a foundation from which you could build off of.

Solution 3

The Sliding window is a problem-solving technique for problems that involve arrays/lists. These problems are easy to solve using a brute force approach in O(n^2) or O(n^3). Using the 'sliding window' technique, we can reduce the time complexity to O(n).

Great article on this is here: https://medium.com/outco/how-to-solve-sliding-window-problems-28d67601a66

So the first thing you want to be able to do is to identify a problem that uses a sliding window paradigm. Luckily, there are some common giveaways:

• The problem will involve a data structure that is ordered and iterable like an array or a string

• You are looking for some subrange in that array/string, like the longest, shortest or target value.

• There is an apparent naive or brute force solution that runs in O(N²), O(2^N) or some other large time complexity.

But the biggest giveaway is that the thing you are looking for is often some kind of optimal, like the longest sequence or shortest sequence of something that satisfies a given condition exactly.

Solution 4

To add to the previous answers here are some more resources which illustrates this concept very well.

This youtube video is the best that I have found on this topic.

Here are the list of questions on leetcode which can be solved using this technique

The sliding window is one of the most frequent topic which is asked in the coding rounds in the top companies so it is definitely worth spending some time to master this.

View more solutions

Comments

[Alexandre C.]

Are you talking about this kind of windows ? I don't see the link with geometry.

[Don Roby]

Explaining the connection won't be possible unless you describe the geometry problem.

[Janac Meena]

No, we're talking about this type of window: plygem.com/wp-content/uploads/2018/09/T3_Horizontal_Slider.g‌​if

[Farbod Ahmadian]

Here is an example: leetcode.com/problems/…

[Ezio]

Amazing illustrations. Thank you for taking the time to do this.

[Adam Zerner]

@Ezio I really appreciate the compliment, thank you. Figuring out illustrations like these is really something I have to do for myself in order to understand it :)

[Ezio]

Absolutely. We are computer programmers but we have to master the art of problem-solving using pen and paper.

[T J]

In the second illustration, shouldn't the golden dot be in second. slide? (1st index instead of 0) or am I missing something?

[Adam Zerner]

@TJ The first row in the second illustration represents let currSum = getSum(arr, 0, 4);. So, the sum of the first five dots. Then from there, to slide the window, we're 1) subtracting the dot in the first column and 2) adding the dot in the sixth column, so that's why the the dots in the first and sixth columns are lit up for the second row.

[Peter]

Hi ,I have a question about sliding window. For example, I have 1 year of information and I am using a 4 month window to analyse it. There are variables that change throughout time. If I am analysing 4 months in the middle of the year, do I use the window size to calculate the metrics for the 4 months, or do I use the variable value at the end of the window that corresponds to 6 or 7 months of information calculated? In this case I am refering to a variable that grows one month at a time.

[aioobe]

Your question is a bit unclear, but suppose you have the following situation: [5, 10, 7, 13, 19, 14, 3, 13, 17, 10, 22, 2] for January, February, ..., December. If your window size is 4, the middle of the year will have this window: [19, 14, 3, 13]. That's all. If you're calculating a running average for example, the average at the middle of the year would be (19+14+3+13)/4. Did this answer your question?

[PartOfTheOhana]

@AdamZerner What tools do you use to make these visualizations?

[Adam Zerner]

@PartOfTheOhana I used Sketch which is kind of a lightweight version of Photoshop. As an alternative, I recently came across Excalidraw which is free and also seems like a good option for visualizations like this.

[Peter]

It certainly gave me more insight. I would like to extend by giving this example: there are 6 months and 3 clients. Client no.1 exists from the beggining, client no.2 appears on the third month and client no.3 appears on the fifth month. The idea would be to use a sliding window to calculate a monthly mean for example. My question is since the sliding window moves a month, the mean for the clients will varies if the window catches months in which they are present in all of them? If not clear I can elaborate.

[inckka]

@AdamZerner At the first code snippet where you have for (let j = i; j <= i + 5; j++) isn't the loop runs 6 times? We need to run 5 times right?

[Stef]

This should be marked as the correct answer - the other answers are about "convolution" rather than about this sliding window algorithm.

[Tan Nguyen]

This should be accepted answer

[Amitesh Bharti]

@AdamZerner 10/10, this illustration is very helpful. With this level of clarity, I think you should write a book on design & DS.

[Adam Zerner]

@AmiteshBharti That's very nice of you to say, thanks! :)

[Ronny Fitzgerald]

Thank you so much. You really made my day because I was struggling with this.

[Adam Zerner]

Glad to hear @RonnyFitzgerald!

[Omkar Shetkar]

@AdamZerner - Amazing explanation. Thanks a lot!