Sliding Window
Uses a moving window to work with contiguous parts of an array or string.
The Approach
- Initialize a 'window' with two pointers, left and right, at the start of the data.
- Expand the window by moving the right pointer to add elements.
- While the window meets a certain condition, update your result (e.g., max value, min length).
- If the window becomes invalid, shrink it from the left by moving the left pointer.
- Repeat until the right pointer has processed the entire dataset.
Types of Sliding Window
Fixed-Size Window
The window size is constant. Used for problems like finding the max sum of a fixed-size subarray.
5
2
8
2
4
7
L
R
Initialize window
Variable-Size Window
The window grows and shrinks. Used to find the smallest or largest window that meets a criteria.
5
2
8
2
4
7
L
R
Initialize window
Frequency-Based Window
Window size is determined by element counts inside it, often using a HashMap.
5
2
8
2
4
7
L
R
Initialize window
Common Problems
Longest Substring Without Repeating Characters
Sliding Window
Minimum Size Subarray Sum
Sliding Window