Sliding Window Algorithm: Complete Interview Guide
Master the sliding window pattern — fixed vs variable windows, when to expand and shrink, and top interview problems.
What is the sliding window technique?
The sliding window technique maintains a range (window) over a sequence and slides it through the data to find an optimal subarray or substring. Instead of recalculating from scratch for every position, the window incrementally adds and removes elements, reducing many O(n²) problems to O(n).
If a problem involves contiguous subarrays or substrings with some constraint (maximum length, minimum sum, no repeated characters), the sliding window is almost certainly the right approach. It is one of the most frequently tested patterns in coding interviews.
Fixed-size window
In a fixed-size window, the window length k is given. You initialize the window with the first k elements, then slide it by adding the next element and removing the element that falls off the left end.
Example: maximum sum subarray of size k
Compute the sum of the first k elements. Then for each subsequent position, add the new right element and subtract the old left element. Track the maximum sum seen. This runs in O(n) instead of O(n×k) with brute force.
Example: find all anagrams in a string
Maintain a character frequency map for the pattern and a frequency map for the current window. When the window reaches the pattern length, compare the maps. Slide by adding the right character and removing the left character, updating the frequency map each time. With a match counter, comparisons reduce to O(1) per slide.
Variable-size window
In a variable-size window, you expand the right pointer to grow the window and contract the left pointer to shrink it. The window size changes dynamically based on a constraint. This is the more common and more challenging variant.
The template
Initialize left = 0. Iterate right from 0 to n-1. At each step, add the element at right to the window state. While the window violates the constraint, remove the element at left and increment left. Update the answer. This template works for both "find the longest valid window" and "find the shortest valid window" problems — only the update step differs.
Example: longest substring without repeating characters
Use a hash set to track characters in the current window. Expand right by adding the new character. If it already exists in the set, shrink from the left until it does not. The answer is the maximum window size seen. This runs in O(n) since each character is added and removed at most once.
Example: minimum window substring
Given strings s and t, find the minimum window in s that contains all characters of t. Use a frequency map and a match counter. Expand right to include characters. When all characters are matched, try shrinking from the left while maintaining the match. Track the smallest valid window. This is one of the harder sliding window problems and a favorite in interviews at top companies.
When to recognize a sliding window problem
The problem mentions contiguous subarrays or substrings. It asks for the longest, shortest, maximum, or minimum satisfying some condition. The brute force involves checking all O(n²) subarrays. The constraint can be tracked incrementally as the window changes.
If the problem asks about subsequences (not contiguous), sliding window does not apply — use dynamic programming or two pointers instead. Contiguity is the key signal.
Sliding window with additional data structures
Some problems require augmenting the basic sliding window with a hash map (character frequencies), a monotonic deque (sliding window maximum), or a sorted structure (median of sliding window). The window logic stays the same — the extra structure tracks a property of the current window that would be expensive to recompute.
For example, the sliding window maximum problem uses a monotonic deque that maintains elements in decreasing order. When the window slides, elements smaller than the new element are removed from the back, and expired elements are removed from the front. The front of the deque is always the maximum. This gives O(n) overall.
Practice problems
Fixed window: maximum average subarray, find all anagrams in a string, permutation in string. Variable window: longest substring without repeating characters, minimum window substring, longest repeating character replacement, fruit into baskets, subarrays with k different integers. Work through these in order — each adds a new complexity layer.
Common mistakes
Forgetting to update the window state when shrinking from the left. Using the wrong condition for expanding vs. shrinking. Not handling the case where the window becomes empty. And a subtle one: updating the answer at the wrong point — for "longest" problems, update after shrinking; for "shortest" problems, update during shrinking.
Ready to ace your next interview?
Phantom Coder gives you real-time AI assistance, invisible to screen sharing.
Download for macOS — $99/mo