Identifying variable sized sliding window pattern

Some specific problems where we need to return a single result after aggregating the results (which may be aggregated) from all subarrays in an array can be solved using the variable-sized sliding window technique. In these problems, we can often skip calculating results for some subarrays by identifying when to expand, contract, or move the window. These are generally medium or hard problems, as we need to make some critical observations and prove that skipping some subarrays does not affect the correctness of the solution.

If the problem statement or its solution follows the generic template below, it can be solved by applying the variable-sized sliding window technique.

Example

Let's consider the following problem as an example to better understand how to identify and solve a problem using the variable-sized sliding window technique.

Problem statement: Given an integer array `arr` find the subarray with the largest sum and return the sum.

Brute force solution

The brute-force solution to this problem is to use nested loops to find the sum of all possible subarrays. If the sum of any subarray is greater than the maximum seen so far, we update the maximum sum value. Below is an execution of the brute force solution on an array.

The implementation of the brute force solution is given as follows.

Though the solution is correct, it requires nested loops and has a time complexity of O(N^2) in any case.

Variable sized sliding window solution

The problem description fits the template for variable-sized sliding window problems as given below. 

By closely observing the problem, we can see that we don't need to calculate the sum of all subarrays to find the subarray with the maximum sum. Let's look at the algorithm in more detail, and we will look at the proof of correctness later in the lesson.

We initialize start and end to 0 to create a sliding window and iterate using end until we reach the end of the array. We create variables sum and maxSum to aggregate the sum of all items in the current window and keep track of the maximum sum seen so far. In each iteration, we add the item at end to the sum and update maxSum if sum is greater than the maximum seen so far. If the sum turns negative at any point, we set start = end + 1 to effectively contract the window size back to 0 when the window expands at the end of the iteration. We also set sum = 0 to reset the sum as the window size is now 0.

Below is the execution of the variable-sized sliding window technique to find the maximum sum subarray of an array.

The variable-sized sliding window solution skips all subarrays starting between start+1 and end and all subarrays starting at start and ending beyond end from maximum sum consideration. We will look at the proof of correctness of this solution later in the lesson.

The implementation of the variable-sized sliding window solution is given below.

As the code above demonstrates, using the variable-sized sliding window technique, we solve the problem in a single pass in linear O(N) time.

Proof of correctness

Consider we have an array arr, and a window denoted by start and end (including start and excluding end) somewhere in the array such that sum(start, i) is non-negative for all i such that start <= i < end. This will be the invariant that we will maintain throughout the execution.

Now consider adding the item at the index end turns the sum negative, i.e., the sum(start, end) is negative.

If the invariant holds, we can prove that all the following subarrays can never have the maximum sum and be ignored.

1. Subarrays starting at start and ending beyond end

Consider a subarray starting at start and ending beyond end denoted by the index b. We can prove that sum(start, b) can never be the maximum sum. This is because sum(end+1, b) will always be greater as sum(start, end) is negative.

2. Subarray starting between start+1 and end and ending beyond end

Consider a subarray starting between start + 1 and end (including both) and ending beyond end denoted by a and b. We can see that sum(a, b) can never be the maximum sum because it will always be less than sum(end+1, b) as sum(a, end) will always be negative. This is because sum(start, end) is negative and, as per our invariant, sum(start, a-1) is non-negative, which means sum(a, end) is negative.

3. Subarray starting between start+1 and end and ending at or before end

Consider a subarray starting between start + 1 and end (including both) and ending at or before end denoted by a and b. We can see that sum(a, b) can never be the maximum sum, as it can never be greater than sum(start, b) since sum(start, a-1) is non-negative as per our invariant.

Conclusion

We can conclude from the three cases above that if the invariant holds, the following subarrays can be skipped

1. All subarrays starting at start and ending beyond end. (From 1 above)
2. All subarrays starting between start+1 and end, including both. (From 2 and 3 above)

Conversely, this means that only the following subarrays should be checked for the maximum sum.

1. Subarrays starting at start and ending before end.
2. Subarrays starting after end.

The variable-sized sliding window technique does precisely this by setting start = 0 and end = 0 to initialize a window of zero size for which the invariant holds true. We then expand the window using end and maintain the invariant as we iterate. In each iteration, we consider the sum(start, end) for the maximum sum and at any point if sum(start, end) turns negative, we set start = end + 1 and end = end + 1 to skip all subarrays starting between start+1 and end and all subarrays starting at start and ending beyond end.

Since the invariant is maintained throughout the run, and we consider sum(start, end) for a maximum sum in each iteration, we are guaranteed to find the maximum sum and only skip subarrays that can never have the maximum sum.

Example problems

Most problems in this category are medium or hard; a list of a few is given below.

• Consecutive ones
• Product conundrum
• Maximum subarray sum
• Consecutive ones with K flips

We will now solve these problems to understand the variable-size sliding window technique better.