PatternsIntermediate9 minO(n) time · O(k) spaceFree
Pattern - Sliding Window
Grow a window right, shrink it left - O(n) instead of O(n^2). The pattern behind Longest Substring Without Repeating Characters and Minimum Window Substring.
01 / 05
What is a sliding window?
A subarray tracked by two indices - left and right - that only ever move forward. Instead of recomputing every subarray from scratch (O(n^2)), you extend right one step at a time and shrink left only when the window breaks a rule. Every element enters and leaves the window once: O(n).
Why is the naive all-subarrays scan slow?