Sliding window (variable)
Why it exists
Problem: Finding a variable-length contiguous sequence that satisfies a condition (e.g., shortest subarray with sum >= target). A naive approach tries all pairs of indices, taking O(n^2) time.
Better idea: Use a sliding window with two pointers (left and right). Expand the right pointer until the condition is met. Then, shrink the left pointer as long as the condition holds to find the optimal length. Since both pointers only move forward, this takes O(n) time.
Mental model
Like a caterpillar crawling over leaves. The front (right pointer) stretches forward to satisfy the condition. Once it has enough, the back (left pointer) scrunches forward to see how tight it can get without losing the meal.
Initialize both `lo` and `hi` pointers at the start. The right pointer (`hi`) moves forward to expand the window and add elements to the running sum. As soon as the sum reaches or exceeds the target, you record the window length. Then, you try to shrink the window by moving the left pointer (`lo`) forward, updating the minimum length if it still meets the target, until the sum drops below the target. Both pointers only ever move forward, which is why it stays O(n) despite the nested-looking shape.
Repeated decision: Does the window still satisfy the constraint -- expand right if not yet violated, shrink from left if violated?
Explanation
A variable-size sliding window is used when you need to find the longest, shortest, or optimal contiguous subarray that meets a certain constraint. Instead of a fixed length, the window dynamically grows and shrinks.
The algorithm uses two pointers, usually `lo` and `hi`. The `hi` pointer expands the window to the right until the condition is satisfied. Once satisfied, the `lo` pointer shrinks the window from the left as long as the condition holds. This shrinking phase is crucial for finding the shortest valid subarray (or dropping invalid elements for longest valid subarray problems).
Let's hand-trace on the array `[2, 4, 1, 5, 3, 6]`, target = 11:
expand: hi=0, sum=2 < 11
expand: hi=1, sum=6 < 11
expand: hi=2, sum=7 < 11
expand: hi=3, sum=12 >= 11 -> record len=4, best=4
shrink: remove arr[0]=2, sum=10 < 11 -> stop shrinking, lo=1
expand: hi=4, sum=13 >= 11 -> record len=4, best still 4
shrink: remove arr[1]=4, sum=9 < 11 -> stop, lo=2
expand: hi=5, sum=15 >= 11 -> record len=4, best still 4
shrink: remove arr[2]=1, sum=14 >= 11 -> record len=3, best=3
shrink: remove arr[3]=5, sum=9 < 11 -> stop, lo=4
Done: shortest qualifying window is [3..5] length 3.
The window grows and shrinks; both pointers only ever move FORWARD, which is why it stays O(n) despite the nested-looking shape. Even though there is a `while` loop inside a `for` loop, the `lo` pointer moves at most `n` times across the entire algorithm.
Common mistakes
- Resetting the left pointer: Resetting `left` back to the start after a violation (turns it O(n^2)). The left pointer should only move forward.
Recall questions
- Why is the variable sliding window O(n) despite having a nested loop?
- What is the repeated decision made at each step in a variable sliding window?
- When do you expand the right pointer, and when do you shrink the left pointer?
Questions & answers
Find the shortest subarray with sum at least target. Why can we use a sliding window?
Because the array only contains positive numbers, the window sum increases as we expand right and decreases as we shrink left. This monotonic property allows us to find the shortest valid window by moving pointers strictly forward.
Approach: Mention the monotonicity requirement for the sliding window to work.
What happens to the sliding window approach if the array contains negative numbers (and you want sum >= target)?
The sliding window fails because the running sum is no longer monotonic. Expanding the window might decrease the sum, and shrinking it might increase it. You would need a different approach, like prefix sums with a monotonic queue.
Approach: Highlight that variable sliding window relies on monotonic changes.
Continue learning
Previous: Sliding window (fixed)
Next: Recognizing sliding window
Related: Recognizing sliding window
Related: Sliding window (fixed)