Overview
A sliding window is a maintained range of consecutive elements within a sequence. Instead of recalculating information for every possible range from scratch, the algorithm updates the current window as its left or right boundary moves.
How it works
Initialize the left and right boundaries of the window.; Expand the right boundary to include new elements.; Update the information maintained for the current window.; If the window violates the required condition, move the left boundary forward.; Record the answer whenever the current window satisfies the problem's requirements.; Continue until every relevant position has been processed.
Key concepts
Contiguous subarrays; Substrings; Window boundaries; Fixed-size windows; Variable-size windows; Window expansion
Types
name: Fixed-Size Window; description: The window always contains a specified number of elements.; examples: Maximum sum of any subarray of size k; Average of consecutive elements; name: Variable-Size Window; description: The window expands or contracts according to a condition.; examples: Longest substring without repeating characters; Smallest subarray with a target sum under suitable input conditions
Time complexity
operation: Fixed-size window traversal; complexity: O(n); operation: Variable-size window traversal; complexity: Often O(n) when each boundary moves only forward
Space complexity
O(1) auxiliary space for a window that maintains only a fixed number of aggregate values. Additional data structures may require more space.
Example
array: 2; 1; windowSize: 3; problem: Find the maximum sum of a consecutive subarray of length 3.; windows: elements: 2; 1; sum: 8; elements: 1; 5; sum: 7; result: maximumSum: 9; subarray: 5; 1