# Sliding Window

## Introduction

## Pitfalls

### Issues with pointer boundaries

Be mindful of potentially forgetting important boundary conditions of the `while`

loop for variable-width sliding window solutions. For example, the solution to one of the homework problems could easily fail if `while left <= right and curr > k:`

were changed to just `while curr > k:`

:

`def max_subarray(nums, k):`

left = curr = ans = 0

for right in range(len(nums)):

curr += nums[right]

while left <= right and curr > k:

curr -= nums[left]

left += 1

curr_window_length = right - left + 1

if curr_window_length > ans:

ans = curr_window_length

return ans

The problem specifies that `nums`

is a list of *positive* integers and that `k`

is an integer. But what if `k`

is a negative integer? For example, what if `nums = [1, 2, 3]`

and `k = -2`

? Since `curr`

is initialized to `0`

, the lowest possible value of `curr`

is, in fact, `0`

. Hence, if `k`

is negative, it will *always* be the case that `curr > k`

, thus resulting in what would be an infinite `while`

loop. But since we try to compute `nums[left]`

and `left`

is being incremented for every iteration of the `while`

loop, we will actually end up with a `IndexError: list index out of range`

error as soon as `left`

has been incremented past the length of `nums`

.

We do not *always* have to have such a condition for our `while`

loop. For example, the solution to another homework problem does not require such a condition because it isn't even possible for the `left`

pointer to surpass the `right`

pointer. Simply put: try to practice vigilance. For example, the following solution looks promising for LC 713:

`class Solution:`

def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:

if k == 0:

return 0

left = ans = 0

prod = 1

for right in range(len(nums)):

prod *= nums[right]

while prod >= k:

prod //= nums[left]

left += 1

ans += right - left + 1

return ans

But what if `nums = [1, 1, 1]`

and `k = 1`

? Then the `while`

loop will continue to execute until `left`

has been incremented so that `nums[left]`

throws an error when `left`

becomes out of range.

## Problems and exercises

### LeetCode

- LC 713. Subarray Product Less Than K
- LC 643. Maximum Average Subarray I
- LC 1004. Max Consecutive Ones III
- LC 2348. Number of Zero-Filled Subarrays

### Warmups

#### Maximum sum subarray of size k

**Problem:** Given an integer array `nums`

and an integer `k`

, find the sum of the subarray with the largest sum whose length is `k`

.

**Solution:** The phrasing of the problem indicates a fixed-width sliding window approach may be fruitful. We can either build the window outside the main loop:

`def find_best_subarray(nums, k):`

curr = 0

# window is built here

for i in range(k):

curr += nums[i]

ans = curr

# window is updated here

for i in range(k, len(nums)):

curr += nums[i] - nums[i-k]

ans = max(ans, curr)

return ans

Or we can build the window within the main loop:

`def find_best_subarray(nums, k):`

curr = ans = 0

for i in range(len(nums)):

# window is built here

if i < k:

curr += nums[i]

# window is updated here

else:

curr += nums[i] - nums[i-k]

ans = max(ans, curr)

return ans

**Analysis:** tbd

### Basics

TBD

### Homework

#### Length of longest subarray whose sum is less than or equal to k

**Problem:** Given an array of positive integers `nums`

and an integer `k`

, find the length of the longest subarray whose sum is less than or equal to `k`

.

**Solution:**

`def max_subarray(nums, k):`

left = curr = ans = 0

for right in range(len(nums)):

curr += nums[right]

while left <= right and curr > k:

curr -= nums[left]

left += 1

curr_window_length = right - left + 1

if curr_window_length > ans:

ans = curr_window_length

return ans

**Analysis:**

Let's consider a concrete example:

`nums: [1, 3, 4, 2, 4, 1, 2, 6]`

k: 9

Below is an illustration of how the 3-step template produces a solution (note how the window shrinks or expands based on whether or not the constraint is satisfied; a subarray with a ~~strike through it~~ indicates the subarray violates the constraint and has to be resized):

```
[1, 3, 4, 2, 4, 1, 2, 6]
left: 0, right: 0, curr: 1, ans: 1, window --> [1]
left: 0, right: 1, curr: 4, ans: 2, window --> [1, 3]
left: 0, right: 2, curr: 8, ans: 3, window --> [1, 3, 4]
left: 0, right: 3, curr: 10, ans: 3, window -->
```~~[1, 3, 4, 2]~~
left: 1, right: 3, curr: 9, ans: 3, window --> [3, 4, 2]
left: 1, right: 4, curr: 13, ans: 3, window --> ~~[3, 4, 2, 4]~~
left: 2, right: 4, curr: 10, ans: 3, window --> ~~[4, 2, 4]~~
left: 3, right: 4, curr: 6, ans: 3, window --> [2, 4]
left: 3, right: 5, curr: 7, ans: 3, window --> [2, 4, 1]
left: 3, right: 6, curr: 9, ans: 4, window --> [2, 4, 1, 2]
left: 3, right: 7, curr: 15, ans: 4, window --> ~~[2, 4, 1, 2, 6]~~
left: 4, right: 7, curr: 13, ans: 4, window --> ~~[4, 1, 2, 6]~~
left: 5, right: 7, curr: 9, ans: 4, window --> [1, 2, 6]

Now let's make explicit step-by-step use of our three-step template with the above illustration as a guide.

**Define window boundaries**

1. Define pointers

`left`

and`right`

that bound the left- and right-hand sides of the current window, respectively, where both pointers usually start at`0`

.

Start by initializing `left`

and `right`

to be `0`

:

`def max_subarray(nums, k):`

left = right = 0

return

**Add elements to window by moving right pointer**

2. Iterate over the source array with the

`right`

bound to "add" elements to the window.

If we want to use `right`

to iterate over the source array, `nums`

in this case, then we can more effectively initialize `right`

to be `0`

by means of `for right in range(len(nums))`

than simply `right = 0`

. The "window" in this case is the subarray whose length is to be maximized while keeping the sum of its elements to be less than or equal to `k`

. So what we really care about is keeping track of

- the sum generated by a window's elements
- the length of the window that generated the sum.

We'll use `curr`

to denote the sum generated by a window's elements (since the sum varies based on which window is being considered). And we'll use `ans`

to keep track of the length of the longest subarray whose elements sum to a value less than or equal to `k`

. Here's a starting point:

`def max_subarray(nums, k):`

left = curr = ans = 0

for right in range(len(nums)):

curr += nums[right]

return

**Remove elements from window by checking constraint and moving left pointer**

3. Whenever the constraint is broken, "remove" elements from the window by incrementing the

`left`

bound until the constraint is satisfied again.

So far we have defined our `left`

and `right`

pointers, and we are set to use `right`

to iterate over the source array and add elements to the window. But now, whenever the constraint is broken (i.e., whenever `curr > k`

), we need to determine how to effectively increment/use `left`

to *remove* elements from the window until the constraint is satisfied again (i.e., `curr <= k`

). All while making sure we use `ans`

to keep track of the length of the longest subarray that satisfies the constraint.

The following code accomlishes exactly this:

`def max_subarray(nums, k):`

left = curr = ans = 0

for right in range(len(nums)):

curr += nums[right]

while curr > k:

curr -= nums[left]

left += 1

curr_window_length = right - left + 1

if curr_window_length > ans:

ans = curr_window_length

return ans

Note which lines of code correspond to each step in the template:

**Step 1:**Lines`2`

and`4`

involve initializing`left`

and`right`

to`0`

, respectively.**Step 2:**Lines`4`

and`5`

involve using`right`

to iterate over`nums`

and add elements to the window, respectively.**Step 3:**Whenever the constraint is broken (line`7`

), "remove" elements from the window (line`8`

) by incrementing the`left`

bound (line`9`

) until the constraint is satisfied again (line`7`

).

Finally, lines `11-13`

do not correspond to a specific step per se. They're simply necessary in the context of this problem (i.e., keeping track of the longest subarray whose elements sum to a value less than or equal to `k`

). They could also be combined into a single line if desired: `ans = max(ans, right - left + 1)`

.

#### Length of longest substring containing only 1 after at most one operation

**Problem:** You are given a binary substring `s`

(a string containing only `"0"`

and `"1"`

). An operation involves flipping a `"0"`

into a `"1"`

. What is the length of the longest substring containing only `"1"`

after performing at most one operation?

For example, given `s = "1101100111"`

, the answer is `5`

. If you perform the operation at index `2`

, the string becomes `"1111100111"`

.

**Solution:**

`def longest_substring(s):`

left = curr = ans = 0

for right in range(len(s)):

if s[right] == "0":

curr += 1

while curr > 1:

left += 1

if s[left] == "0":

curr -= 1

ans = max(ans, right - left + 1)

return ans

**Analysis:** Because the string can only contain `"1"`

and `"0"`

, another way to look at this problem is "what is the longest substring that contains **at most one** `"0"`

?". This makes it easy for us to solve with a sliding window where our condition is `window.count("0") <= 1`

. Again, we can use an integer `curr`

that keeps track of how many `"0"`

s we currently have in our window.

The main trick here is knowing how to effectively shrink the window. Once `curr == 2`

, we need to resize our window and get rid of the left-most `0`

. We do this by incrementing the `left`

pointer--once the `left`

pointer has been moved beyond the left-most `0`

, then we are back in business.

### Exam

#### LC 713. Subarray Product Less Than K

**Problem (LC 713):** Given an array of positive integers `nums`

and an integer `k`

, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than `k`

. For example, given the input `nums = [10, 5, 2, 6]`

, `k = 100`

, the answer is `8`

. The subarrays with products less than `k`

are:

`[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]`

**Solution:**

`class Solution:`

def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:

if k == 0:

return 0

left = ans = 0

prod = 1

for right in range(len(nums)):

prod *= nums[right]

while left <= right and prod >= k:

prod //= nums[left]

left += 1

ans += right - left + 1

return ans

**Analysis:** This is a tricky problem. It may help to consider a concrete example other than the one given with the problem statement. Suppose we have the following:

`nums = [10, 5, 20, 3, 7, 2, 50]`

k = 100

If we were trying to find the length of the largest subarray whose product was less than `k`

, then this would be a standard variable-width sliding window problem:

`class Solution:`

def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:

left = ans = 0

prod = 1

for right in range(len(nums)):

prod *= nums[right]

while left <= right and prod >= k:

prod //= nums[left]

left += 1

ans = max(ans, right - left + 1)

return ans

The highlighted line above is what we are used to for this kind of problem. For our specific example, the output would be `3`

, which would be in reference to the subarray `[3, 7, 2]`

, which has a product of `3 * 7 * 2 = 21 < 100`

. But we want the *number* of *contiguous* subarrays where the product of all the elements in the subarray is strictly less than `k`

.

With `nums = [10, 5, 20, 3, 7, 2, 50]`

as above, how many subarrays of `nums`

are there? Since `nums`

has a total of `7`

elements, it follows that `nums`

has a total of $\frac{7(7+1)}{2}=28$ subarrays. Of these `28`

subarrays, how many of them, when all of their elements are multiplied together, have a product strictly less than `k`

?

The key insight to easily answering this question, in the context of using a sliding window approach, may be more easily understood if we define things more precisely. Specifically, let each subarray of `nums`

be denoted by the interval notation $I[\alpha,\beta]$, where $0\leq\alpha\leq\beta\leq n-1$; hence, `nums`

itself may be represented by $I[0, n-1]$. Let $P_{I[\alpha,\beta]}$ denote the product of all elements for some interval $I[\alpha,\beta]$. We're interested in finding the *number* of all intervals $I[\alpha,\beta]$ for which

Now for the clever part: if subarray/interval $I[\alpha,\beta]$ of `nums`

satisfies the given constraint, then how many subarrays can we count towards the total we ultimately want to report? The naive answer would be $\frac{(\beta-\alpha)(\beta-\alpha+1)}{2}$, the total number of subarrays of $I[\alpha,\beta]$. But we need to be careful not to overcount.

For example, in the context of our problem, where `nums = [10, 5, 20, 3, 7, 2, 50]`

, consider the subarray `[20, 3, 7]`

. This subarray does not satisfy the constraint of the problem, but `[20, 3]`

and `[3, 7]`

do. If we counted the number of subarrays for each of these constraint-satisfying intervals towards the total, then we would count `6`

because intervals `[20, 3]`

and `[3, 7]`

generate subarrays `[20], [3], [20, 3]`

and `[3], [7], [3, 7]`

, respectively. But note how we counted `[3]`

twice. We overcounted!

How do we avoid overcounting? *By looking at the right endpoint of each constraint-satisfying interval.* Specifically, if $I[\gamma,\lambda]$ satisfies $P_{I[\gamma,\lambda]}<k$, then *the total number of subintervals of nums that have $\lambda$ as their right endpoint is necessarily $\lambda-\gamma+1$* (i.e., the length of the subinterval). We add this number to our running total for every valid subinterval we come across. How does this ensure we avoid overcounting?

Consider the valid subarray $I[\gamma,\lambda]$. Here is an illustration of the $\lambda-\gamma+1$ subarrays that get added to the total (what each subarray looks like is illustrated by means of underbraces; note that $\gamma,\ldots,\lambda$ all refer to *indices* of `nums`

while $I$-notation involves the actual subarrays of `nums`

that are highlighted in the underbraces):

Note how *every* subarray above has $I[\lambda]$ as an element since $I[\lambda]$ is each subinterval's right endpoint. If we add an element to the window in question, then the index range for our window changes from $[\gamma,\lambda]$ to $[\gamma,\lambda+1]$. If $P_{I[\gamma,\lambda+1]}<k$, then how many subarrays should be added to our total? Our observations above indicate that the total added should be $(\lambda+1)-\gamma+1$. But how can we be certain that none of the subarrays coming from $I[\gamma,\lambda+1]$ have already been counted from $I[\gamma,\lambda]$? Because *every* subarray from $I[\gamma,\lambda+1]$ will have the element $I[\lambda+1]$ present as its right endpoint while *not a single subarray* from $I[\gamma,\lambda]$ could possibly have $I[\lambda+1]$ present:

Hence, for every subinterval we come across that satisfies the given constraint, we'll simply add its length to the overall running total.

Our code, in light of the notes above, becomes the following (note how it involves only changing a single line):

`class Solution:`

def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:

left = ans = 0

prod = 1

for right in range(len(nums)):

prod *= nums[right]

while left <= right and prod >= k:

prod //= nums[left]

left += 1

ans += right - left + 1

return ans

Let's return to our concrete example of `nums = [10, 5, 20, 3, 7, 2, 50]`

with `k = 100`

. If we add the line

`print(f'Window: [{nums[left]}, {nums[right]}], Index range: [{left}, {right}]')`

right above or below the highlighted line in the solution above, then we get the following output:

`Window: [10, 10], Index range: [0, 0]`

Window: [10, 5], Index range: [0, 1]

Window: [20, 20], Index range: [2, 2]

Window: [20, 3], Index range: [2, 3]

Window: [3, 7], Index range: [3, 4]

Window: [3, 2], Index range: [3, 5]

Window: [50, 50], Index range: [6, 6]

In terms of our $I$-notation, where $I[\alpha,\beta]$ represents the window with index range $[\alpha,\beta]$, we have the following:

Hence, for our concrete example, a total of 12 subarrays satisfy the constraint.

## Staging area

### Brain dump

- In general, a "sliding window" really refers to a technique of increasing the efficiency with which subitems may be assessed or processed against some constraint. This usually means taking a brute force algorithm from $O(n^2)$ or $O(nk)$ to just $O(n)$.
- Fundamentally, the ingenuity of the technique lies in how elements of subitems (i.e., "windows") are processed efficiently and without duplication of effort or computation. The idea is to avoid unnecessary work (i.e., computation).
- 2-step template for problems involving fixed-width windows:
- Should the creation of the window happen before/outside the main loop?
- Should the creation of the window happen within the main loop?

- 3-step template for problems involving variable-width windows:
- Define window boundaries (i.e., where
`left`

and`right`

should start, most often at index`0`

) - Add elements to window by moving
`right`

pointer - Remove elements from window by checking constraint and moving
`left`

pointer **Note:**Usage of a`while`

loop involving the removal of elements from a window and incrementing of the`left`

pointer is considered to be $O(1)$ due to amortized analysis.

- Define window boundaries (i.e., where
**Clever trick:**Whenever you see a problem asking for*the number of subarrays*that satisfy some condition, think of this: at each index, how many subarrays satisfying the constraint*end*at such an index? You may be fortunate as in LC 713 to exploit some useful mathematical properties.

### Implementation

Uses two-pointers.

### Definition

From a structural standpoint, sliding windows are nothing more than iterables (i.e., an object capable of returning values one at a time) with ordered elements; that is, a sliding window is some sort of structure whose elements are ordered and may be iterated over. Most often this structure is an array or string.

### General algorithm

#### Variable window size

`function fn(arr):`

left = 0

for right in [0, arr.length - 1]:

while left < right AND condition from problem not met:

Do some logic to "remove" element at arr[left] from window

left++

Do some logic to "add" element at arr[right] to window

Amortized analysis indicates the algorithm above will run in $O(n)$ time--the `while`

loop is considered to be $O(1)$ since the `while`

loop can only iterate $n$ times in total for the entire algorithm (`left`

starts at `0`

, only increases, and never exceeds `n`

). So even though the `while`

loop could run `n`

times on a single iteration of the `for`

loop, such an instance would necessarily mean that the `while`

loop would not run at all for the other iterations of the `for`

loop.

#### Fixed window size

When it is clear that a problem calls for a fixed-width sliding window approach, we can either build the initial window outside the main loop or within the main loop, where the "main loop" refers to where we put the logic for maintaining the window. Sometimes one approach is more appropriate than another.

For example, in LC 643, it's much cleaner to build the initial window *outside* the main loop:

`class Solution:`

def findMaxAverage(self, nums: List[int], k: int) -> float:

curr = 0

for i in range(k):

curr += nums[i]

ans = curr

for i in range(k, len(nums)):

curr += nums[i] - nums[i-k]

ans = max(ans, curr)

return ans / k

Of course, we can build the initial window *within* the main loop as well, but it is not as clean:

`class Solution:`

def findMaxAverage(self, nums: List[int], k: int) -> float:

curr = 0

ans = float('-inf')

for i in range(len(nums)):

if i < k:

curr += nums[i]

if i == k-1:

ans = max(ans, curr)

else:

curr += nums[i] - nums[i-k]

ans = max(ans, curr)

return ans / k

##### Window built outside main loop

`// first approach`

function fn(arr, k):

curr = some data type to track the window

// build the first window

for i in [0, k - 1]:

Do something with curr or other variables to build first window

ans = answer variable, might be equal to curr here depending on the problem

for i in [k, arr.length - 1]:

Add arr[i] to window

Remove arr[i - k] from window

Update ans

return ans

##### Window built within main loop

`// second approach`

function fn(arr, k):

curr = some data type to track the window

ans = answer variable

for i in range(len(arr)):

if i >= k:

Update ans

Remove arr[i - k] from window

Add arr[i] to window

Update ans

return ans // Alternatively, you could do something like return max(ans, curr)

// if the problem is asking for a maximum value and curr is tracking that.

## Identifying pattern relevance

A sliding window approach may be appropriate when a problem involves satisfying some constraint or condition in reference to a *sub*-item of a given size where that subitem may be a subarray, substring, etc.