Okay, Move Along
The Fixed-Size Sliding Window Pattern/Technique
The fixed-size sliding window pattern optimizes algorithms that involve searching an array or string for a consecutive subsection, of a given size, that satisfies a given condition. It can also be considered a variation of the two pointers pattern.
To solve problems like these, we could apply a brute force solution with a nested loop, but it would produce O(n²) time complexity at best. Applying the fixed-size sliding window pattern can reduce the time complexity to O(n) and space complexity to O(1).
Let’s get a move on
In this pattern, two pointers create a window that represents the current subsection of the data structure. One pointer is the leading edge and the other pointer is the trailing edge. This window, or chunk, is evaluated to see if it satisfies the given condition. The window slides along the data structure (by incrementing the pointers) to create a new window. The new window is now evaluated to see if it satisfies the given condition.
The window continues to slide until the leading edge reaches the end. Once the window has reached the end, the requested output is returned.
We are moving in the right direction when the problem:
- involves a data structure that is iterable (arrays, strings, etc.)
- has a size constraint (e.g. of given length
k) - asks to find a subsection (substring/subarray) that meets a desired condition/target value (e.g. max/min)
Example
Sample Problems
- Maximum Average Subarray I
- Maximum Number of Vowels in a Substring of Given Length
- Subarray of length K whose concatenation forms a palindrome
- Subarray of length K having concatenation of its elements divisible by X
- Maximum distinct prime factors of elements in a K-length subarray
📚 Resources 👀
