Coding interview pattern
Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
The idea
How the sliding window pattern works
The sliding window pattern turns a naive nested-loop scan over every subarray (which is quadratic or worse) into a single linear pass. Instead of recomputing a property for each window from scratch, you maintain a window with two boundaries and update an aggregate (a sum, a count, a frequency map) incrementally as the window moves. When the right edge advances you add the new element; when the left edge advances you remove the old one. The work per step is constant, so the whole scan is linear.
There are two flavours. A fixed-size window slides a window of constant length k across the array, which fits problems like maximum sum of any k consecutive elements. A variable-size window grows the right edge to satisfy a condition and shrinks the left edge when the condition breaks, which fits problems like the longest substring without repeating characters or the smallest subarray with a sum at least a target.
The mental model that prevents bugs: the window always represents a valid (or about-to-be-validated) candidate, and you only ever move boundaries forward. Because neither pointer ever moves backward, the amortised cost stays linear even though the inner shrink loop looks nested.
Recognition
When to reach for it
- The input is a contiguous sequence (array or string) and you want a subarray or substring.
- The question asks for a maximum, minimum, longest, shortest, or count over contiguous runs.
- A brute-force solution would re-scan overlapping subarrays repeatedly.
- You can update the answer for a window in O(1) when one element enters or leaves.
Cost
Time & space complexity
| Operation | Time | Space |
|---|---|---|
| Fixed-size window scan | O(n) | O(1) or O(k) |
| Variable-size window scan | O(n) | O(k) for the frequency map |
| Brute force (what you replace) | O(n^2) or O(n*k) | O(1) |
Worked example
Walkthrough: Longest substring without repeating characters
- 1Keep a set (or last-seen index map) of characters currently in the window, and two pointers left and right both starting at 0.
- 2Advance right one character at a time, adding each new character to the window.
- 3If the new character is already in the window, shrink from the left, removing characters, until the duplicate is gone.
- 4After each step the window is duplicate-free, so update the best length with right minus left plus one.
- 5Because left and right each only move forward across the string, the total work is linear.
Translatable skeleton
The shape in pseudocode
Language-agnostic on purpose. Translate it to your language of choice.
left = 0; for right in range(n): add(s[right]); while invalid(): remove(s[left]); left += 1; best = max(best, right - left + 1)Practice
Curated problem set
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Maximum Average Subarray I | Easy | Canonical fixed-size window. |
| Longest Substring Without Repeating Characters | Medium | Classic variable window with a seen-set. |
| Minimum Size Subarray Sum | Medium | Shrink while the sum stays at least the target. |
| Permutation in String | Medium | Fixed window plus frequency-count matching. |
| Longest Repeating Character Replacement | Medium | Window valid while length minus max-freq is at most k. |
| Minimum Window Substring | Hard | Variable window with a need-count, the hardest of the set. |
Avoid these
Common pitfalls
- Forgetting to shrink the window, which silently degrades to O(n^2).
- Updating the best answer before the window is valid, off by one.
- Mishandling the frequency map when the same character enters and leaves.
- Using a fixed window when the size actually varies, or vice versa.
In the interview
How to communicate it live
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Say the word window out loud and state whether it is fixed or variable before you write code; that single sentence tells the interviewer you have recognised the pattern rather than stumbled into it.
Narrate the invariant the window maintains, for example the window always contains no repeated characters, because the invariant is what justifies that the answer is correct at every step.
When you shrink, explain that the left pointer never moves backward, which is the argument for why the whole thing is linear despite the inner loop looking nested.
Also searched as
sliding window leetcode - longest substring pattern - fixed and variable window
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- Competitive Programmer's Handbook: two pointers method and sliding window minimum (8.1, 8.3) Antti Laaksonen, CSES
- Lecture 9: Hashing II (rolling hash over a fixed window) MIT OpenCourseWare, 6.006 Introduction to Algorithms
- collections: Container datatypes (deque) Python Software Foundation
Keep going
Related patterns
These techniques share moves with this one, so the practice carries over.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
- Breadth-First Search (BFS)
Explore level by level with a queue; the natural fit for shortest paths on unweighted graphs.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.