Sliding Window
Maintain a window over a contiguous subarray or substring, expanding or shrinking it to satisfy a constraint. Avoids recomputing from scratch on every step.
Time
O(n)
Space
O(1) or O(k)
Recognize it when
- Find max/min/average of contiguous subarrays of size k
- Longest/shortest subarray/substring satisfying a condition
- Problem mentions "contiguous" sequence
- "At most K distinct elements" or "exactly K" pattern
Questions — ordered by difficulty
Maximum Average Subarray I
Given an integer array nums and integer k, find a contiguous subarray of exactly length k that has the maximum average value, and return that value. Example: nums=[1,12,-5,-6,50,3], k=4 → 12.75 (the subarray [12,-5,-6,50] has average 51/4 = 12.75).
Minimum Size Subarray Sum
Given an array of positive integers and a target, find the minimal length of a subarray whose sum is ≥ target.
Longest Substring Without Repeating Characters
Find the length of the longest substring that contains no repeating characters.
Longest Repeating Character Replacement
Given a string and integer k, find the length of the longest substring where you can replace at most k characters to make all characters the same.
Permutation in String
Given strings s1 and s2, return true if s2 contains a permutation of s1.
Minimum Window Substring
Find the minimum window in string s which will contain all characters of string t.
Sliding Window Maximum
Return the maximum value in each sliding window of size k as it moves across the array.