Understanding the variable sized sliding window pattern

Some problems may require us to find the output of an aggregate function over all subarrays of an array and then further aggregate the results from all subarrays into a single value. To solve these problems, we would need to run fixed-sized sliding windows of all sizes from 1 to N(size of the array) through the array to aggregate results for all subarrays, which is inefficient.

However, for some problems, we may only need to find results for some subarrays and skip the remaining. These problems can be solved by the variable-sized sliding window technique, which contracts or expands the window in each iteration as it slides through the array. It is a powerful technique that can solve many problems in a single pass that would otherwise need nested loops to compute subarrays.

Variable sized sliding technique

The variable-sized sliding window technique uses two variables start and end to maintain a window in the array and a variable aggregate that always holds the aggregated value of f over the current window.

We initialize aggregate with some default value dictated by the problem and start with start = 0 and end = 0 that denotes a zero-sized window. We iterate until end reaches the end of the array and, in each interaction, do some or all of the operations given below.

1. Update aggregate with item at end

We update aggregate by adding the contribution of arr[end] to it so that it can be processed later in this iteration.

2. Process the aggregate

The value stored in aggregate is the aggregated value of the function f over the subarray from start to end. We process it as dictated by the problem.

3. Contract the window by incrementing start

If we can skip all remaining subarrays starting at start (the ones ending beyond end)  we can increment start by 1, which also contracts the window. We also update aggregate to remove the contributions of the item removed from the window.

4. Expand the window by incrementing end

If we want to consider the next subarray starting at start (from start to end+1)  in the next iteration, we can increment end by one, which also expands the window. We don't add the contribution of the newly added item to aggregate yet, as that will be done in the next iteration.

Algorithm

The algorithm given below outlines the generic variable-sized sliding window technique.

• Step 1: Initialize two variables, `start` and `end` to 0.
• Step 2: Initialize `aggregate` to some initial value dictated by the problem.
• Step 3: Loop until `end` < `arr.size()` and do the following
  • Step 3.1: Check if we should compute aggregate
    • Step 3.1.1: Add contribution of `arr[end]` to `aggregate`
  • Step 3.2: Process `aggregate`
  • Step 3.3: Check if we should contract the window
    • Step 3.3.1: Remove the contribution of `arr[start]` from `aggregate`
    • Step 3.3.2: Increment `start`
  • Step 3.3: Check if we should expand the window
    • Step 3.3.2: Increment `end`

Implementation

Given below is the generic code implementation of the variable-sized sliding window technique on an array arr with 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 using start and end and with each iteration, we either move, expand, or contract it. Both start and end are initialized with 0, and at least one of them moves forward in each iteration, which means there can be a maximum of 2*N iterations of the outer while loop before both start and end reach the end of the array. And so, in the worst case, both start and end will iterate the entire array, leading to O(2*N) ~ O(N) runtime complexity, assuming that both function f and g have constant O(1) time complexity. In the best case, end reaches the end of the array after N iterations which also has linear O(N) runtime complexity.

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

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 variable-sized sliding window technique and walk through an example to better understand it.