Identifying the fixed sized sliding window pattern
The fixed-size sliding window technique can only be applied to some specific problems. These are generally easy problems in which we must compute some aggregate function's output for all fixed-sized subarrays in an array. We may often have to aggregate these results further using some other function to get the solution to the problem. If the problem statement or its solution follows the generic template below, it can be solved by applying the fixed-sized sliding window technique.
f for all subarrays of size k. We should be able to add/remove the contribution of an item from the aggregate computed by f.Example
Let's consider the following problem as an example to better understand how to identify and solve a problem using the fixed-sized sliding window technique.
Problem statement: Given an array `arr` and an integer `k`, we need to find the maximum average of all subarrays of size `k`.
Find the maximum average of all subarrays of size k = 4
Brute force solution
The brute-force solution to this problem is to use a loop to traverse the array from start to N-k (where N is the size of the array) using a variable start. In each iteration, use another loop to iterate from start to start + k- 1. to compute the average of k sized subarray starting at start. We update the maximum if we find the average of any subarray greater than any averages seen earlier.
The implementation of the brute force solution is given as follows.
C++
Java
Typescript
Javascript
Python
Though the solution is correct, it requires nested loops and has a worst-case time complexity of O(N^2) when k = N / 2 where N is the size of the array.
Fixed sized sliding window solution
The problem description fits the generic template for problems that can be solved using the fixed-sized sliding window technique.
arr, compute the average (function f ) for all subarrays of size k. We can add/remove the contribution of an item from the aggregate computed by the average (function f)We keep the sum of all items in the window instead of the average, as the average can be easily computed from the sum and size of the window. We initialize two variables sum and maxAverage with 0 and -infinite denoting the sum of the current window and the maximum average seen so far.
We then create a window by initalizing start and end to 0 and iterate until end reaches the end of the array. In each iteration, we add the contribution of the item at end and compute the average if needed. If the average of the current window is greater than maxAverage, we update maxAverage. At the end of all iterations, maxAverage will have the maximum average of all subarrays of size k.
Below is an execution of the fixed-sized sliding window solution on an array where k = 4.
Find the maximum average of all subarrays of size 4
The implementation of the sliding window solution is given as follows.
C++
Java
Typescript
Javascript
Python
As the code above demonstrates, using the fixed-sized sliding window technique, we solve the problem in a single pass in linear O(N) time.
Example problems
Most problems that fall under this category are easy problems; a list of a few is given below.
We will now solve these problems to understand the fixed-size sliding window technique better.