Why This Matters
Sliding window is the default pattern for contiguous subarrays and substrings when a constraint can be repaired by moving the left boundary. It replaces "try every interval" with a single pass.
The invariant is the whole technique: the current interval is either valid, or it can be made valid by shrinking from the left without missing a better answer.
Prerequisite Check
Review Arrays and Two pointers. Sliding window is a same-direction two-pointer method where left and right bound a contiguous region.
Learning Objectives
By the end, you should be able to:
- Distinguish fixed-size and variable-size windows.
- State the window invariant before writing code.
- Explain why nonnegative sums create a monotone shrink condition.
- Use hash counts for substring windows.
- Identify when sliding window is invalid and prefix sums or DP are better.
Core Idea
Move right to include new elements. While the invariant is violated, move left to remove old elements. Record the best answer whenever the window is valid.
| Pattern | Invariant | Typical problem |
|---|---|---|
| Fixed window | length is exactly k | max sum of k items |
| At-most constraint | sum/count stays below a limit | longest subarray with sum at most k |
| Distinct window | character counts stay at most one | longest substring without repeats |
| Frequency window | counts meet a target condition | minimum covering substring |
Visual Model
values: [2, 1, 3, 2, 4], limit = 5
[2, 1, 3] sum=6 invalid -> move left
[1, 3] sum=4 valid
[1, 3, 2] sum=6 invalid -> move left
[3, 2] sum=5 valid
The window only moves forward. No element enters or leaves more than once.
Non-Example or Failure Mode
Sliding window does not automatically work when numbers can be negative. A larger window can have a smaller sum after adding a negative number, so the shrink rule is no longer monotone. For arbitrary signed sums, use prefix sums or dynamic programming.
Worked Example
Find the longest subarray with sum at most 5 in [2, 1, 3, 2, 4].
right=0: [2], sum=2, best=1
right=1: [2,1], sum=3, best=2
right=2: [2,1,3], sum=6 -> remove 2 -> [1,3], best=2
right=3: [1,3,2], sum=6 -> remove 1 -> [3,2], best=2
right=4: [3,2,4], sum=9 -> remove 3 -> [2,4], remove 2 -> [4], best=2
LeetCode-Style Problem Patterns
| Pattern | Recognition signal | Move |
|---|---|---|
| Longest valid substring | "longest substring without..." | expand right, shrink duplicate counts |
| Max/min fixed segment | "exactly k consecutive" | maintain rolling sum/count |
| At most K | "at most k distinct" | shrink while count exceeds k |
| Minimum covering window | "smallest substring containing..." | shrink after all requirements are met |
Common Mistakes
| Mistake | Correction |
|---|---|
| Using sliding window on non-monotone constraints. | Check whether moving left predictably repairs validity. |
| Updating the answer while the window is invalid. | Record only after restoring the invariant. |
| Forgetting to decrement frequency counts. | Maintain counts symmetrically as elements enter and leave. |
| Moving both boundaries blindly. | Let the invariant decide when each pointer moves. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What does a sliding window store? | A contiguous interval plus summary state such as sum or counts. |
| Example / non-example | Does sliding window handle arbitrary negative values for sum-at-most problems? | Not by default; monotonicity fails. |
| Computation | Why is the common two-pointer version O(n)? | Each boundary moves forward at most n times. |
| Proof | What invariant justifies discarding the old left element? | Once invalid, every longer window with that left boundary remains invalid under the monotone condition. |
| Transfer | How does substring sliding window differ from numeric windows? | It usually tracks character counts instead of a numeric sum. |
Exercises
Beginner:
- Compute the maximum sum of any fixed-size window of length
3. - Trace longest subarray with sum at most
kfor nonnegative values. - Explain why each element enters and leaves at most once.
Intermediate:
- Implement longest substring without repeated characters.
- Convert "at most K distinct characters" into a frequency-window invariant.
Challenge:
- Show a counterexample where negative values break the sum-at-most sliding-window algorithm.
Diagram Recommendation
Type: window-boundary trace.
Caption: "Right expands the interval; left repairs the invariant."
Purpose: Make it obvious why the algorithm is linear and why monotonicity matters.
Implementation Task
Implement one numeric window and one string-frequency window. Write down what makes each window valid.
Run sliding-window examples
This cell checks a nonnegative sum window and a substring-without-repeats window.
Output will appear here.
Next Topics
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- Princeton Algorithms, Analysis of Algorithms: https://algs4.cs.princeton.edu/14analysis/
- Python documentation, dictionary type: https://docs.python.org/3/library/stdtypes.html#mapping-types-dict
- Python documentation, sequence types: https://docs.python.org/3/library/stdtypes.html#sequence-types-list-tuple-range