## 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 **fixed-length** sliding windows.

## Fixed-Length Sliding Window

When you know the length of the subsequence you are looking for, you can use a fixed-length sliding window. The concept is similar to the variable-length sliding window, but the implementation is a bit simpler, as during each iteration, you both add and remove an element from the window to maintain its fixed size.

### Problem: Maximum Sum of Subarray with Size K

###### DESCRIPTION

Given an array of integers nums and an integer k, find the maximum sum of any contiguous subarray of size k.

**Example**:
Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: The subarray with the maximum sum is [5, 1, 3] with a sum of 9.

We start by extending the window to size k. Whenever our window is of size k, we first compute the sum of the window and update max_sum if it is larger than max_sum. Then, we contract the window by removing the leftmost element to prepare for the next iteration. Note how we calculate the sum of the window incrementally by adding the new element and removing from the previous sum.

#### Solution

def max_subarray_sum(nums, k):max_sum = 0state = 0start = 0for end in range(len(nums)):state += nums[end]if end - start + 1 == k:max_sum = max(max_sum, state)state -= nums[start]start += 1return max_sum

### Template

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

def fixed_length_sliding_window(nums, k):state = # choose appropriate data structurestart = 0max_ = 0for end in range(len(nums)):# extend window# add nums[end] to state in O(1) in timeif end - start + 1 == k:# INVARIANT: size of the window is k here.max_ = max(max_, contents of state)# contract window# remove nums[start] from state in O(1) in timestart += 1return 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

### Fixed-Length

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

Maximum Sum of Subarrays of Size K | Easy |

Max Points You Can Obtain From Cards | Medium |

Max Sum of Distinct Subarrays Length k | Medium |

Loading comments...