Dynamic Sliding Window
Grow until the window is valid, then shrink to find the smallest valid answer.
0 of 3 problems solved
Dynamic Sliding Window
Grow until the window is valid, then shrink to find the smallest valid answer.
- •Am I searching for the smallest valid window?
- •Do I expand first, then shrink while still valid?
- •Am I updating the answer every time the target is reached?
This is still sliding window, but now the goal changes. You are not looking for the biggest valid window. You are looking for the smallest window whose sum is big enough. That means you expand to the right until the window becomes valid, then you immediately try to shrink it from the left to see if you can keep the rule while making it smaller. It is like tightening a belt one notch at a time after it finally fits.
Once the window reaches the target, shrinking is where the real optimization happens.
- 1Grow the window by moving the right pointer and adding values to the running sum.
- 2As soon as the sum is at least the target, record the current window size.
- 3Then move the left pointer to shrink the window while it is still valid.
- 4Keep the smallest valid length seen so far.
Stopping as soon as you hit the target misses shorter valid windows hiding inside the current one.
Maximum Average Subarray I
Fixed window of size k. Pre-compute the initial sum, then slide by subtracting the exiting element and adding the entering one.
Minimum Window Substring
Expand right until all required characters are present, then shrink left for the smallest valid window. Track character counts and a satisfied-character counter.