The core idea: reuse the overlap
The brute-force way to find the maximum sum of every contiguous subarray of size k is to add up k numbers, slide over by one, and add up k numbers again, repeated n times for O(n·k) work. But look closely: two neighbouring windows share all but two of their elements. The sliding window pattern exploits that overlap. When the window moves one step right, you subtract the element that just left and add the element that just entered. Each move is O(1), so the whole scan is O(n).
That single insight — carry information forward instead of rebuilding it — is the entire pattern. Everything else is bookkeeping: a running sum, a character count, or a hash set of what is currently inside the window. It is much easier to feel when you watch the window glide across the array one frame at a time.
Fixed windows vs. variable windows
There are two flavours. A fixed-size window has a constant length k; the left and right edges advance together in lockstep, and you report an answer at every position. This solves problems like the maximum sum subarray of size k or the average of every window of k readings.
A variable-size window grows and shrinks to satisfy a condition. You expand the right edge to pull new elements in, and whenever the window violates its constraint (or once you want to minimize it), you contract from the left with a while loop until the constraint holds again. "Longest substring without repeating characters" and "smallest subarray whose sum is at least a target" are variable-window problems. The variable version is usually paired with a hash map or counter that records exactly what the window contains.
How to spot one
Reach for a sliding window when the problem is about a contiguous subarray or substring and asks for a longest, shortest, maximum, minimum, or a count over ranges — especially if it mentions "of size k" or "at most K distinct." The tell-tale sign is a naive solution that repeats work across overlapping ranges. If the target need not be contiguous, sliding window will not apply, and you usually want dynamic programming instead.
def longest_unique_substring(s: str) -> int:
seen = {} # char -> most recent index
left = 0
best = 0
for right, ch in enumerate(s):
# If ch repeats inside the window, jump left past its last spot
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
best = max(best, right - left + 1)
return bestTime is O(n) in the best, average, and worst case — there is no degenerate input, because each of the two pointers only ever moves forward, never backward, so every element enters and leaves the window at most once. Space is O(1) for running-sum or fixed-size windows and up to O(k) when you track the window's distinct elements in a hash set or map, where k is the window size or alphabet. The hash map adds a constant-factor overhead but does not change the linear time bound.
When to use it
- Finding the maximum or minimum sum (or average) of any contiguous subarray of a fixed size k.
- Finding the longest or shortest substring or subarray that satisfies a condition, such as no repeating characters or at most K distinct values.
- Counting or measuring something over every contiguous window — anagram matches, subarrays with a given sum of positive numbers, or streaming averages.
- Any time you catch yourself writing nested loops over contiguous ranges where the inner work overlaps between adjacent ranges.
Watch out for
- Applying it when the answer need not be contiguous. Sliding window only works on contiguous ranges; for arbitrary subsets or non-adjacent selections you need dynamic programming or another approach.
- Shrinking with an if instead of a while. In variable-size problems you must contract from the left until the constraint is fully restored before recording an answer, which usually means a while loop, not a single conditional step.
- Assuming it works with negative numbers for sum-based shrinking. "Smallest subarray with sum ≥ target" relies on the sum increasing as you add elements; with negatives that monotonicity breaks, and you need prefix sums or a different technique.
Sliding window is one of the most frequently tested patterns in phone screens and onsite rounds. Expect classics like Longest Substring Without Repeating Characters, Minimum Window Substring, Maximum Sum Subarray of Size K, Longest Substring with At Most K Distinct Characters, and Find All Anagrams in a String. Interviewers are watching for a few specific things: that you recognize the brute-force nested loop is O(n²) and can articulate why the window avoids recomputation, that you choose fixed versus variable correctly, that you manage the shrink condition with a while loop rather than an if, and that you can justify the amortized O(n) runtime by noting each pointer moves forward at most n times. Handling edge cases (empty input, all-identical characters), stating space cost clearly, and naming the invariant the window maintains ("the window always holds a valid substring") is what separates a strong candidate from one who merely memorized a template.