Sliding Window

Sliding Window is a technique used for common problems that have to do with a subarray or sublist.
Often we are asked to calculate something among all contiguous subarrays. At the least it comes with two Pointers and usually you keep track of the previous best solution.

The Two Pointers usually move in the same direction and never overtake each other.

Giveaway for sliding window:

Two important questions:

Given an array, find the average of all contiguous subarrays of size ‘K’ in it.


Array: [1, 3, 2, 6, -1, 4, 1, 8, 2], K=5


Output: [2.2, 2.8, 2.4, 3.6, 2.8]

BF Solution

We would loop through the array and count the sum of every subarray with the length of K and divide the sum by K.

Time complexity

For every element in the input array N we are calculating the sum of its next K elements, therefore Big O is (N * K).


We can optimize the Algorithm as whenever we ware calculating the sum of K elements we have overlapping elements that don't need to be recalculated.
Instead we can remove the leftmost element and add the rightmost element, by doing that the Time complexity comes down to O (N).