What is the Sliding Window Technique?
Understand the sliding window technique with fixed and variable window examples, Python code, and common interview pitfalls.
Expected Interview Answer
The sliding window technique maintains a contiguous subrange of an array or string, expanding and contracting its boundaries as it scans, to solve subarray or substring problems in O(n) time instead of re-examining every subrange from scratch.
A window is defined by a start and end index; the end pointer advances to include new elements, and the start pointer advances to shrink the window when a constraint is violated or a better answer is confirmed. Because each element is added to the window once and removed at most once, the total work stays linear even though it conceptually explores many subranges. It is the standard pattern for maximum-sum-subarray, longest-substring-without-repeats, and minimum-window-substring problems. Interviewers use it to see if you can avoid the O(n²) or O(n³) brute-force scan of all subranges.
- Turns O(n²) subarray scans into O(n)
- Handles fixed-size and variable-size windows
- Avoids recomputation by incrementally updating window state
- Standard tool for substring and subarray problems
AI Mentor Explanation
A commentator tracking a batter’s best 6-over scoring stretch does not recompute the total from ball one every time — they add the runs from the new over entering the window and subtract the runs from the oldest over leaving it. The window of six overs slides forward one over at a time, always covering a contiguous stretch. This is exactly the sliding window technique: maintain a running total for a contiguous range and update it incrementally instead of resumming.
Step-by-Step Explanation
Step 1
Choose fixed or variable window
Fixed-size windows (like moving averages) have constant width; variable windows grow and shrink based on a constraint.
Step 2
Expand the window
Move the right boundary forward, incorporating the new element into the running window state.
Step 3
Contract when needed
Move the left boundary forward to shrink the window when a constraint is violated or an answer is confirmed.
Step 4
Track the best result
Update a running best (max sum, min length, etc.) each time the window satisfies the target condition.
What Interviewer Expects
- Distinguishing fixed-size vs variable-size window problems
- Incrementally updating window state instead of recomputing from scratch
- Correctly identifying when to shrink the window
- Stating O(n) time complexity with a justification
Common Mistakes
- Recomputing the window sum from scratch on every slide
- Forgetting to shrink the window when a constraint is violated
- Using sliding window on data where contiguity does not apply
- Mishandling window boundaries, causing off-by-one length errors
Best Answer (HR Friendly)
“The sliding window technique tracks a contiguous chunk of data — like the last few elements of an array — and updates it incrementally as it moves forward instead of re-scanning everything each time. It is the standard way to solve problems about the best or longest contiguous stretch, like finding the longest substring without repeating characters, in linear time.”
Code Example
def length_of_longest_substring(s):
seen = {}
left = 0
best = 0
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return bestFollow-up Questions
- How does the sliding window technique differ from the two pointer technique?
- How would you find the minimum window substring containing all characters of a target string?
- How do you compute a fixed-size moving average with a sliding window?
- What data structure helps track character counts inside a variable window?
MCQ Practice
1. What is the time complexity of the sliding window solution for longest substring without repeats?
Each character is added and removed from the window at most once, giving O(n).
2. When should the left boundary of a variable sliding window move forward?
The left boundary advances to shrink the window and restore the constraint.
3. Which problem type is best suited to the sliding window technique?
Sliding window is designed for contiguous-range problems like subarrays and substrings.
Flash Cards
Sliding window technique — Tracks a contiguous range with incrementally updated state as boundaries move, achieving O(n) time.
Fixed-size window — Window width stays constant, e.g. moving averages.
Variable-size window — Window grows and shrinks based on a constraint, e.g. longest valid substring.
Key efficiency trick — Add the entering element and remove the exiting element instead of recomputing the whole window.