DSA & Algorithms
Part 3 of 21 · DSA Interview PatternsSliding Window — Fixed & Variable Windows for Subarrays
Fixed and variable sliding windows for subarray/substring constraints in O(n).
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
The answer is a contiguous subarray or substring
Prefer
Expand right, shrink left, stay O(n)
Every index enters and leaves at most once. The window state is a sum or a frequency map.
- Fixed length k slides by adding one and dropping one.
- A variable window shrinks only while the constraint is broken.
- The best answer updates only when the window is valid.
Alternative
Recompute the range from scratch
A fresh scan of every [L, R] is correct and quadratic.
- Negative numbers break a shrink-when-sum-is-large rule.
- Exactly K is not the same function as at most K.
- A non-contiguous subset is a different pattern.
Keep the window honest
Right grows. Left catches up. The invariant is the whole interview.
- 1
Expand right
Add nums[right] or s[right] to the window state. - 2
Shrink while invalid
Move left until the constraint holds again. - 3
Record if this window counts
Longest, shortest, or a boolean hit.
Overview
Fixed and variable sliding windows for subarray/substring constraints in O(n).
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use for contiguous subarrays/substrings with a constraint you can maintain while expanding the right end and shrinking the left.
Recognition cues
- longest/shortest subarray with at most/exactly K distinct
- sum less-or-equal target / product constraints
- anagrams in a string (fixed window)
- minimum window substring
Mental model
Decisions
- 1
Step 1 Expand right - add s[right] to the window state
- nextStep 2 Window still valid?
- ?
Step 2 Window still valid?
- noStep 3 Shrink - remove s[left], left += 1
- yesStep 4 Update best with right - left + 1
- negative numbers - shrinking no longer restores validityFailure path - switch to prefix sums plus a hashmap
- 3
Step 3 Shrink - remove s[left], left += 1
- nextStep 2 Window still valid?
- 4
Step 4 Update best with right - left + 1
- nextStep 5 right at the end?
- ?
Step 5 right at the end?
- noStep 1 Expand right - add s[right] to the window state
- yesStep 6 Return best
- 6
Step 6 Return best
- 7
Failure path - switch to prefix sums plus a hashmap
Lesson map
Sliding Window — Fixed & Variable Windows for Subarrays
Fixed and variable sliding windows for subarray/substring constraints in O(n).
Architecture. Step 1 Expand right - add s[right] to the window state Ready. Step 2 Window still valid? Ready. Step 3 Shrink - remove s[left], left += 1 Ready. Step 4 Update best with right - left + 1 Ready. Step 5 right at the end? Ready. Step 6 Return best Ready. Failure path - switch to prefix sums plus a hashmap Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB R["Step 1 Expand right - add s[right] to the window state Ready"] V["Step 2 Window still valid? Ready"] L["Step 3 Shrink - remove s[left], left += 1 Ready"] B["Step 4 Update best with right - left + 1 Ready"] E["Step 5 right at the end? Ready"] A["Step 6 Return best Ready"] F["Failure path - switch to prefix sums plus a hashmap Ready"] R -->|continues| V V -->|no| L L -->|continues| V V -->|yes| B B -->|continues| E E -->|no| R E -->|yes| A V -->|negative numbers - shrinking no longer restores validity| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Each index enters/leaves the window at most once → O(n) time.
- Space O(alphabet) or O(k) for frequency maps.
Common pitfalls & interview traps
LeetCode drill (real problems)
- Longest Substring Without Repeating Characters
- Minimum Window Substring
- Longest Repeating Character Replacement
- Permutation in String
- Max Consecutive Ones III
- Sliding Window Maximum
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Fixed vs variable window?
Answer
Fixed keeps length k; variable shrinks/grows to satisfy a constraint.
Why O(n)?
Answer
Left and right each move at most n times.
Exactly K distinct trick?
Answer
count(at most K) minus count(at most K-1). This counts subarrays; it does not give the longest or shortest exactly-K window.
When window fails?
Answer
Non-contiguous subsets; negative sums needing Kadane or prefix.
Min window substring key?
Answer
Need-count map; shrink only when all required chars are satisfied.
Interview tip?
Answer
State the invariant: window [L,R] is always valid or always a candidate.