Sliding Window
Fixed Length Sliding Window
Count: 10
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 subarray/substring 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
Visualization
Python
Try these examples:
def max_subarray_sum(nums, k):max_sum = float('-inf')state = 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
start
max subarray sum of size k
0 / 16
Template
Here's a template you can use as a starting point for solving problems with a fixed-length sliding window.
Solution
Python
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 subarray/substring in an array or string that satisfies a certain constraint.
If you know the length of the subarray/substring 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
When practicing these problems, it is important to think about the appropriate data structure state to store the contents of the current window. Make sure it supports both:
- Adding and removing elements from the window in O(1) time.
- Checking if the window is valid in O(1) time.
Dictionaries and sets are often the best choices.
Fixed-Length
Done | Question | Difficulty |
|---|---|---|
Easy | ||
Medium | ||
Medium |
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.