Menu
Sliding Window
Introduction
Sliding window is an optimization technique generally applied in problems involving arrays and strings. When applied correctly, it can reduce the time complexity of an algorithm by a factor of O(n). For example, it can be used to optimize algorithms time complexity from O(n^2) to O(n) or O(n^3) to O(n^2) etc. This is done by reusing the computation done for the previous window for the next window which eliminates the need of the inner for loop. Please take a look at the example below to understand this further.
Example
Let us go over an example to understand how we can optimize the runtime of any algorithm using sliding window technique.
Let’s say we are given an array A consisting of n positive integers, and a positive integer K. We need to print the sum of all the integers for consecutive subarrays of size K. for example, if the given array is [1, 2, 3, 4, 5, 6] and K = 3, then I need to print the sum of following subarrays :
1. [1, 2, 3]
2. [2, 3, 4]
3. [3, 4, 5]
4. [4, 5, 6]
Using brute force approach, I can easily solve this problem using two nested for loops and going over the sum of the consecutive subarrays as shown below:
However, the above approach has a time complexity of O(nk) and in the worst case k = n and time complexity jumps to O(n^2). This technique can be optimized further by using sliding window technique.
Let us denote the sum of the first subarray (from index 0 till 2) as sum[0], sum of second subarray (from index 1 till 3) as sum[1] and so on.
Clearly,
sum[0] = arr[0] + arr[1] + arr[2]
sum[1] = arr[1] + arr[2] + arr[3]
sum[2] = arr[2] + arr[3] + arr[4]
and so on.
We can eliminate the inner for loop in the brute force solution discussed above by rewriting the values of sum[1], sum[2] in terms of it’s previous window/subarray as shown below.
sum[1] = sum[0] – arr[0] + arr[3]
sum[2] = sum[1] – arr[1] + arr[4]
sum[3] = sum[2] – arr[2] + arr[5]
and so on.
Using the above approach, we can remove the inner for loop and reduce the time complexity from O(nk) to O(n). Take a look at the code given below.
