MediumWindow Invariant
Sliding Window
Sliding window solves contiguous subarray or substring problems by expanding and shrinking a range.
Intuition
Maintain a window that satisfies an invariant. Expand to include new data; shrink when the invariant breaks.
Complexity Analysis
Usually O(n) time because each pointer moves forward at most n times. Space depends on window metadata.
Common Mistakes
- Jumping to code before naming the invariant or state being maintained
- Forgetting edge cases such as empty input, one element, duplicates, and negative values
- Using a brute-force approach without explaining how the pattern improves it
Interview Notes
- State the brute force first, then explain the bottleneck and the optimization
- Say the time and space complexity before the interviewer asks
- Walk through one small example and one edge case
Best Practices
- Keep variable names tied to the invariant: left, right, seen, window, slow, fast
- Prefer simple control flow over clever one-liners in interviews
- Write tests for boundary cases after the main solution
Example Problems
- Longest Substring Without Repeating Characters
- Permutation in String
- Minimum Window Substring