## Sliding Window

This technique refers to creating a window that "slides" through an input sequence (typically an array or string).

Sliding windows can be either variable or fixed length. On this page, we'll cover **variable-length** sliding windows by looking at:

- An example problem that illustrates the motivation for each type of sliding window, as well as how to implement it.
- The types of problems for which each type of sliding window is useful, as well as templates you can use as a starting point.
- A list of practice problems (with animated solutions and explanations!) for you to try to build upon the concepts covered here.

### Problem: Fruit Into Baskets

###### DESCRIPTION (credit Leetcode.com)

Write a function to calculate the maximum number of fruits you can collect from an integer array fruits, where each element represents a type of fruit. You can start collecting fruits from any position in the array, but you must stop once you encounter a third distinct type of fruit. The goal is to find the longest subarray where at most two different types of fruits are collected.

**Example**:
Input: fruits = [3, 3, 2, 1, 2, 1, 0]
Output: 4
Explanation: We can pick up 4 fruit from the subarray [2, 1, 2, 1]

We'll walkthrough how to use the sliding window to solve this problem when fruits = [3, 3, 2, 1, 2, 1, 0].

#### Naive Approach

To understand the motivation behind the sliding window pattern, let's start by looking at a naive approach to this problem, which considers every possible subarray in the input, and chooses the longest one with at most 2 distinct fruits.

def fruit_into_baskets(fruits):max_length = 0# i and j are the start and end indices of the subarrayfor i in range(len(fruits)):for j in range(i, len(fruits)):if len(set(fruits[i:j + 1])) <= 2:max_length = max(max_length, j - i + 1)else:# the subarray starting at i is invalid# so we break and move to the next onebreakreturn max_length

This approach considers O(n2) subarrays. For each subarray, it checks if it contains at most 2 distinct fruits by converting it to a set and checking its length, which takes O(n) time, for a total a time complexity of O(n3). We'll gradually improve this approach until we reach the sliding window pattern, which solves this problem in O(n) time.

##### Improvement 1: Build Incrementally

The first improvement is to use a variable to store the contents of the current subarray. We'll use a dictionary state that maps each fruit in the current subarray to the number of times it appears.

This choice of state is key as it allows us to:

- Build the contents of the subarray incrementally. Each time we expand the subarray to include a new fruit, we'll increment the count of that fruit in state, which reuses work from the previous subarray.
- Check if the subarray is valid by checking if state has 2 keys or less.

Since both of these operations take O(1) time, we can now check if a new subarray is valid in O(1) time. This brings the total time complexity of the solution down to O(n2).

def fruit_into_baskets(fruits):max_length = 0# i and j are the start and end indices of the subarrayfor i in range(len(fruits)):state = {}for j in range(i, len(fruits)):state[fruits[j]] = state.get(fruits[j], 0) + 1if len(state) <= 2:max_length = max(max_length, j - i + 1)else:# the subarray starting at i is invalid# so we break and move to the next onebreakreturn max_length

##### Improvement 2: Don't Blow It All Up!

In the above approach, we reset state each time we reach an invalid subarray and break from the inner loop. When the outer loop increments i, we end up rebuilding parts of the same subarray from the previous iteration, which we can see by visualizing the first few steps of the algorithm:

Rather than resetting the contents of state each time we reach an invalid subarray, **we can instead think about removing fruits from the start of the subarray until it is valid again**. This allows us to move onto the next valid subarray while also preserving work we've already done - which brings us to the sliding window pattern.

#### The Sliding Window

We now have enough context to understand the motivation behind the sliding window pattern. The "window" in the sliding window refers to a subarray we are considering to contain the maximum number of fruits we can collect.

##### Initialization

We use two pointers, start and end, to represent the start and end indices of the window. The window is initially empty, and so is the dictionary state that represents the contents of the window. We also initialize a variable max_fruit that represents the maximum amount of fruit we can collect.

##### Iteration

Next we repeatedly extend the current window incrementing end. Each time we do so, we add the fruit at end to state by incrementing its count in the dictionary, and then we compare the length of the window to the current value of max_fruit, and update it if its greater.

##### Contracting the Window

Eventually, we reach a window that is invalid because it contains 3 distinct fruits. Here, we contract the window by decrementing the count of the fruit at start in state, and then incrementing start to contract the window. We contract the window until it is valid again.

At this point, our window is ready to expand again, so we continue iterating until we reach the end of the array, at which point we return max_fruit.

#### Solution

Here's what the final solution looks like:

def fruit_into_baskets(fruits):start = 0state = {}max_fruit = 0for end in range(len(fruits)):state[fruits[end]] = state.get(fruits[end], 0) + 1while len(state) > 2:state[fruits[start]] -= 1if state[fruits[start]] == 0:del state[fruits[start]]start += 1max_fruit = max(max_fruit, end - start + 1)return max_fruit

#### Complexity

- The time complexity of this algorithm is O(n), where n is the length of the input array. end iterates through the array once, and start iterates through the array at most once. Each time either moves, we arrive at a new window, which requires O(1) time to check if its valid.
- The space complexity of this algorithm is O(1), since state never contains more than 3 keys.

### Template

Here's a template you can use as a starting point for solving problems with a variable-length sliding window.

def variable_length_sliding_window(nums):state = # choose appropriate data structurestart = 0max_ = 0for end in range(len(nums)):# extend window# add nums[end] to state in O(1) in timewhile state is not valid:# repeatedly contract window until it is valid again# remove nums[start] from state in O(1) in timestart += 1# INVARIANT: state of current window is valid here.max_ = max(max_, end - start + 1)return max_

## When Do I Use This?

Consider using the sliding window pattern for questions that involve **searching for a continuous subsequence** in an array or string that satisfies a certain constraint.

If you know the length of the subsequence you are looking for, use a fixed-length sliding window. Otherwise, use a variable-length sliding window.

*Examples:*

- Finding the largest substring without repeating characters in a given string (variable-length).
- Finding the largest substring containing a single character that can be made by replacing at most k characters in a given string (variable-length).
- Finding the largest sum of a subarray of size k without duplicate elements in a given array (fixed-length).

## Practice Problems

Question | Difficulty |
---|---|

Longest Substring Without Repeating Characters | Medium |

Longest Repeating Character Replacement | Medium |

Loading comments...