Sliding Window Technique
The Sliding Window technique is an optimization pattern used primarily for arrays and strings. It aims to reduce the use of nested loops and replace them with a single loop, thereby reducing the time complexity from O(N²) to O(N).
Think of a window as a contiguous subset of elements within the array or string. Depending on the problem, this window can either be of a fixed size (e.g., "find the maximum sum of exactly K elements") or a variable size(e.g., "find the smallest subarray whose sum is greater than or equal to S").
1. Fixed-Size Window
In a fixed-size window problem, the size of the window K is given. The window slides over the data structure one element at a time. As the window moves forward by one position, the element that falls out of the left boundary is removed from our running state (e.g., a running sum), and the new element that enters the right boundary is added.
Common Pattern:
- Initialize the window by processing the first
Kelements. - Slide the window by moving the
leftandrightpointers one step forward. - Update the result (e.g., check if the new sum is the maximum).
- Repeat until the
rightpointer reaches the end of the array.
2. Variable-Size Window
In a variable-size window problem, the window size can grow or shrink dynamically based on certain conditions. Typically, we expand the window by moving the right pointer until a condition is met or violated. Then, we shrink the window from the left until the condition is satisfied again.
Common Pattern:
- Start with both
leftandrightpointers at 0. - Expand the window by advancing
rightand updating the running state. - If the condition is violated (e.g., duplicate character found, sum exceeds limit), shrink the window by advancing
leftuntil the condition is valid again. - Keep track of the optimal result (e.g., longest substring length, smallest subarray length).
Why is it O(N)?
Although variable-size sliding window problems often feature a while loop inside a for loop, the overall time complexity is still O(N).
This is because both the left and right pointers only ever move forward. In the worst case, each element is visited at most twice: once when it enters the window (by the right pointer) and once when it leaves (by the left pointer). Therefore, the work done is proportional to 2N, which simplifies to O(N).