Understanding the fixed sized sliding window pattern

Some problems require us to apply an aggregate function to all subarrays of a fixed size in an array and process the results. While using nested loops might be the only way to do this for most problems, there are some problems where we can use the fixed-sized sliding window technique to get the aggregated values of all subarrays in a single pass. These are the problems where the aggregate function also has both addition and removal operations to add and remove the contribution of data items from the aggregated value.

The fixed-sized sliding window technique falls under a broader category of sliding window pattern. In this lesson, we will only learn about the fixed-sized sliding window technique; however, later in the course, we will also learn the variable-sized sliding window technique, another category under the sliding window pattern. 

Fixed sized sliding window technique

Consider a function f such that f(i, j) denotes the aggregated value of f over the subarray from index i to index j (including both).

Now consider we need to apply this function to all subarrays of size k in the given array, i.e. f(0, k-1), f(1, k), .... f(n-k, n-1).

The fixed-sized sliding window technique uses two variables start and end, to maintain a fixed-sized window (subarray). Another variable aggregate holds the output of f when applied over the data items of the current window. We slide the window 1 step to the right in each iteration and update aggregate accordingly. 

For a fixed-sized widow of size k, we initialize start = 0 and end = 0 and iterate until end reaches the end of the array. In each iteration, we add the contribution of arr[end] to the aggregate and then check if the window size end - start + 1 is greater than k. If the window size is greater than k, we remove the contribution of the item at arr[start] from aggregate by using the removal operation for the function f and then contract the current window from the start by incrementing start by 1.

Next, we check if the size of the current window equals k. If size equals k, we process aggregate as dictated by the problem. Finally, we increment end by 1 to expand the window from the end. Below is an example execution of the fixed-sized sliding window technique on an array where k = 4.

The fixed-sized sliding window technique avoids the inner loop by removing the contribution of the removed item using the removal operation for the function and adding the contribution of the newly added item as the window slides. This way, we do not need to recompute the contributions of the common (middle) items to the aggregated result in the moving window.

Algorithm

The algorithm given below outlines the generic fixed-sized sliding window technique for a window of size k.

• Step 1: Initialize two variables, `start` and `end` to 0.
• Step 2: Create a variable `aggregate` to store the aggregated value of a window and initialize it to some default value
• Step 3: Loop while `end` < `arr.size()` and do the following
  • Step 3.1: Add contribution of `arr[end]` to `aggregate`
  • Step 3.2: If the size of the current window (`end` - `start` + 1) is greater than `k` remove the contribution of `arr[start]` from `aggregate` and increment `start` by 1
  • Step 3.2: If the size of the current window (`end` - `start` + 1) is equals `k`, process `aggregate`
  • Step 3.3: Increment `end` by 1

Implementation

Given below is the generic code implementation of the fixed-size sliding window technique on an array arr with window size k using variables start and end as the boundaries of the window.

Complexity Analysis

The algorithm's time and space complexity is easy to understand. We create a sliding window of size k and move it one step at a time until it reaches the end. The variable end iterates from 0 to N-1, where N is the size of the array. So, the runtime complexity is linear O(N) if the function f is a constant time O(1) operation.

Since we do not create a new data structure, the space complexity is constant O(1). 

Best Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Worst Case

• Space Complexity - O(1)
• Time Complexity - O(N)

Later in the course, we will examine techniques for identifying problems that can be solved using the fixed-sized sliding window technique and walk through an example to better understand it.