Sliding Window
Process subsets of arrays or strings using a moving window to avoid redundant computations and achieve optimal time complexity.
Sliding Window is a core pattern in algorithm design, especially useful for array and string problems that involve contiguous elements. Instead of repeatedly recalculating results for every possible subarray, the window “slides” across the data—expanding when needed and shrinking when constraints are violated. This reuse of previous computations makes the approach highly efficient.
There are two primary variations: fixed-size and variable-size windows. Fixed-size windows maintain a constant length, while variable-size windows dynamically grow and shrink based on conditions such as sum, uniqueness, or frequency. Advanced versions combine sliding windows with hash maps or monotonic data structures to handle more complex constraints like frequency tracking or maximum/minimum queries.
Maintain a constant window size while sliding across the array to compute results efficiently.
Expand and shrink the window dynamically based on conditions to find optimal subarrays or substrings.
Use hash maps within a sliding window to track frequencies and optimize substring problems.
Use a monotonic deque to efficiently track maximum or minimum values within a sliding window.