Home » Interview Topics » Sliding Window

# 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.