The Sliding Window Pattern
The sliding window is an indispensable technique for array/string problems, reducing nested loops to a single linear pass (O(N) time complexity). It is highly favored in Google and Amazon interviews.
Key Concepts
- Fixed Window: The window size remains constant (e.g., "Find max sum of subarray of size K").
- Dynamic Window: The window size expands and contracts based on a condition (e.g., "Smallest subarray with sum >= S").
Common Interview Questions
- Longest Substring Without Repeating Characters
- Minimum Window Substring
- Permutation in String
