Sliding window
Keep a stretch of the array that obeys a rule. Grow it on the right, and when the rule breaks, shrink it from the left until it holds again.
Problems worked on this page, and more to practise
- 3. Longest Substring Without Repeating Characters
- 424. Longest Repeating Character Replacement
- 76. Minimum Window Substring
- 904. Fruit Into Baskets
- 1004. Max Consecutive Ones III
- 209. Minimum Size Subarray Sum
- 567. Permutation in String
- 438. Find All Anagrams in a String
- 992. Subarrays with K Different Integers
- 239. Sliding Window Maximum
When should I use a sliding window?
When the answer is one contiguous stretch of an array or string, and making the stretch longer can only push it toward breaking the rule, never back. Longest substring without repeats, at most K distinct values, and a sum target over positive numbers all fit. If elements may be skipped, or a sum target allows negative numbers, it does not apply.
Why is a sliding window O(n) when it has a loop inside a loop?
Count pointer moves across the whole run. The right pointer moves n times. The left pointer only moves forward and never passes the right one, so it also moves at most n times. The inner loop runs once per left move, so in total it runs at most n times, not n times per outer step.
What is the difference between a sliding window and two pointers?
A sliding window is two pointers that move in the same direction and bound a contiguous range whose contents you summarize as you go. The classic two-pointer technique starts at both ends of a sorted array and moves the pointers toward each other. Both keep an invariant about what the pointers rule out.
Why does a sliding window fail with negative numbers?
The window relies on one direction of change: growing makes the sum larger, shrinking makes it smaller. A negative number breaks that, so dropping a prefix that looked too large can throw away exactly what a later negative would have balanced. Use prefix sums with a hash map for sum targets over signed numbers.