Sliding Window: A Practical Interview Guide

Who asks this, and how oftenInterview frequency: High

Most asked at Amazon. Here is how often this pattern shows up in each company's coding rounds.

Amazon

If you remember five things

Everything below is just the defense of these five calls.

The recognition cue. "Contiguous" subarray or substring, plus "longest/shortest/max/min" or "at most K," is the giant flashing sign. See those words together and reach for a window.
Two shapes only. Fixed size (K is given: add one, drop one) and variable size (grow right, shrink left while invalid). Learn both cold.
Incremental state is the whole trick. When the window moves by one, you update a running sum, count, or frequency map in O(1). You never recompute the window from scratch.
O(n) by amortization. Each pointer only moves forward, so total work is bounded by 2n even with a nested-looking while loop. Be ready to say this out loud.
Know the boundary. Windows need monotonicity. Negatives plus a sum target break it, and that is a prefix-sum-plus-hash-map problem, not a window.

1The mental model (what this really is)#

A window is a contiguous chunk of an array or string defined by two pointers: a left edge and a right edge.

Grow by sliding the right edge forward.
Shrink by pulling the left edge forward when the window breaks some rule.
Always contiguous. Never a scattered pick of elements. If the problem lets you pick non-adjacent elements, this pattern does not apply.

The insight that makes it fast: you update, you do not recompute.

When the window moves by one, one element enters on the right and maybe one leaves on the left.
You adjust a running value (a sum, a count, a frequency map) in O(1).
That reuse of work is the entire point of the pattern.

Why it beats brute force, in numbers.

Brute force asks "what is true about the subarray from i to j?" for every pair i, j.
For length n that is about n squared over 2 pairs: roughly 500,000 operations at n = 1,000, and 50,000,000 at n = 10,000.
A window carries the previous answer forward, so at n = 10,000 you do 10,000 steps, not 50,000,000.

A window is a running answer you maintain incrementally as two pointers crawl across the data once.

2How to recognize it (the signals in a problem)#

You are almost certainly looking at a sliding window when these words show up together.

"Contiguous" subarray or substring. The giant flashing sign. Non-adjacent picks mean dynamic programming or greedy, not a window.
"Longest" or "shortest" or "maximum" or "minimum" of some measure over a contiguous run.
A constraint on the window: "at most K distinct characters," "sum equals target," "no repeating characters," "sum at least S."
A count of subarrays that satisfy a property.

A quieter second signal.

You instinctively wrote a nested loop.
The inner loop recomputes a sum or a set over a range.
The data is all non-negative, or the constraint is monotonic.
That recomputation is exactly the waste a window removes.

The one caveat that saves you

Classic variable-size windows rely on monotonicity: growing the window only makes it "worse" in one direction, shrinking only makes it "better." Plain positive-number subarray sums have this. Negatives often break it, and then you need prefix sums plus a hash map instead. Force a window where monotonicity is dead and you will patch forever and still be wrong. I cover that trap in section 5.

The decision flow I run in my head when a new problem lands:

flowchart TD A[Contiguous range asked] -->|no| B[Not a window] A -->|yes| C{Fixed length K given} C -->|yes| D[Fixed window add one drop one] C -->|no| E{Constraint monotonic} E -->|no| F[Prefix sums and hash map] E -->|yes| G[Variable window expand then shrink]

The whole triage in one picture. The first fork (contiguous or not) rules the pattern in or out. The last fork (monotonic or not) is the trap: a "no" there routes you to prefix sums, not a window.

3The template (how it works, with pseudocode)#

Two shapes. Learn both cold, because an interviewer can flip you from one to the other mid-question.

Fixed-size window (window length is a given K):

window_value = aggregate of first K elements
best = window_value

for right in range(K, n):
    window_value += arr[right]          # element enters
    window_value -= arr[right - K]      # element leaves
    best = better(best, window_value)

return best

Variable-size window (the workhorse, size depends on a constraint):

left = 0
state = empty          # a sum, a count, or a frequency map
best = initial

for right in range(n):
    add arr[right] to state            # grow the window

    while window is invalid:            # fix the violation
        remove arr[left] from state
        left += 1

    best = update(best, right - left + 1)   # record a valid window

return best

Read the variable-size template three times, then burn in the rhythm.

Expand on the right every single step.
Shrink from the left only while the window is illegal.
Record the answer when the window is legal.

Keep it a while, not an if

The shrink loop is where people get sloppy. One shrink step is rarely enough to restore validity. An if silently passes the easy cases and fails on clustered violations (think "aabbaa"). Default to while unless you have a specific reason not to.

Pause before the worked example: why is this O(n) and not O(n squared), given there is a loop inside a loop?

Reveal the answer

Amortization. The left pointer only ever moves forward, and it can never pass the right pointer. Across the entire outer loop, left advances at most n times total, so the inner while runs at most n times total, not n times per step. Each element enters once and leaves at most once. Total pointer movement is bounded by 2n. That is the exact sentence interviewers want to hear when they poke the nested loop.

4A worked example (walk through one problem step by step)#

Problem: Longest substring without repeating characters. Given a string, find the length of the longest run with all unique characters. This is LeetCode 3, the single most common window question I have seen in real loops.

Let me use "abcabcbb". I keep a set of characters currently in my window, a left pointer, and a best length, and I walk right across the string.

right = 0, char a. Not in set. Add it. Window "a", length 1. best = 1.
right = 1, char b. Not in set. Add it. Window "ab", length 2. best = 2.
right = 2, char c. Not in set. Add it. Window "abc", length 3. best = 3.
right = 3, char a. Already present, window invalid. Shrink: remove arr[left] = a, move left to 1. Now add the new a. Window "bca", length 3. best stays 3.
right = 4, char b. Already present. Remove arr[left] = b, move left to 2. Add b. Window "cab", length 3. best stays 3.
right = 5, char c. Present. Remove c, move left to 3. Add c. Window "abc", length 3. best stays 3.
right = 6, char b. Present. At left = 3 the window is "abc" for indices 3,4,5. Remove a (left to 4), remove b (left to 5), now b at index 6 can enter. Window "cb", length 2. best stays 3.
right = 7, char b. Present. Remove c (left to 6), b still there, remove b (left to 7), add b. Window "b", length 1. best stays 3.

Answer: 3, for "abc".

Here is the same idea in runnable Python so you can see the exact bookkeeping:

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

What to notice at right = 3 and right = 6.

The while loop ran until the window was legal again.
Each character was added once and removed at most once, so left only ever moves forward.
Total pointer movement is at most 2n. That is why this is O(n), not O(n squared).

The line that proves you understand it

Interviewers love "why is this linear if there is a nested loop?" The answer is amortization: each pointer crosses the array once, so the inner while cannot run more than n times total across the whole outer loop. Say it in those words and the complexity question is closed.

5Variations and gotchas (what the interviewer throws next)#

Fixed vs variable.

K is given? Fixed size: add one, drop one, done.
"Longest or shortest satisfying X"? Variable size.

At most K vs exactly K.

"Exactly K distinct" is hard to window directly.
Clean move: exactly(K) = atMost(K) - atMost(K-1), where each atMost is a standard window.
See "exactly," reach for this subtraction. Subarrays with K Different Integers (LeetCode 992) is the canonical test.

Counting subarrays.

When the property is monotonic, every valid window ending at right contributes right - left + 1 new subarrays.
Add that count each step instead of tracking a max.

Shrink conditionally vs always.

For "shortest window that covers X" (Minimum Window Substring, LeetCode 76), expand until valid, then shrink while still valid to tighten.
Same template, different record point: this is the mirror image of the longest-window logic.

State choices. Pick the cheapest structure that validates the window in O(1) amortized.

A running sum for numeric constraints.
A frequency hash map for character or element counts.
A count of some property plus a few variables.

From the interviewer's chair

When I ask "now count the subarrays instead of the longest one," I am checking whether you own the template or memorized one problem. The window machinery does not change at all. Only the record step changes: best = max(...) becomes total += right - left + 1. If you rebuild the whole solution from scratch, I learn you pattern-matched rather than understood.

The negative-numbers trap.

"Subarray sum equals K" with negatives is NOT a sliding window problem.
Growing the window can decrease the sum, so the monotonic logic collapses.
That one wants prefix sums and a hash map (LeetCode 560).
The moment you see negatives plus a sum target, drop the window.

6Complexity#

Time is O(n) for almost every true sliding window problem.

Each of the two pointers advances across the input at most once.
Per-step work (updating a sum, map, or count) is O(1) amortized.
The atMost(K) - atMost(K-1) variants run two passes, still O(n).

Space depends on the state.

O(1) when the state is a running sum or a fixed set of counters.
O(k) or O(min(n, alphabet)) when you hold a frequency map, where the alphabet might be 26 lowercase letters, 128 ASCII characters, or the number of distinct values allowed.
For most interview strings that map is effectively constant, but say "O(alphabet size)" out loud. It shows precision, and precision separates a hire from a weak hire on the complexity question.

~5,000x

Why you bother with the windowAt n = 10,000, brute force does about 50,000,000 steps and the window does 10,000. You trade a little space for a full order of magnitude in speed, and that trade is almost always the right call.

7Mistakes that cost people the round#

Using if where you need while to shrink. One shrink step is often not enough. If left only moves once per right move, you pass easy cases and fail on clustered duplicates. Default to while.
Forgetting to update state on both ends. People add the entering element but forget to remove the leaving one, or decrement a count without deleting the zero entry from the map. Both corrupt the validity check silently, and silent bugs are the worst kind under time pressure.
Recording the answer at the wrong moment. For longest, record after the window is made valid. For shortest, record inside the shrink loop while it is still valid. Mixing these gives off-by-one answers that look almost right.
Off-by-one on window length. It is right - left + 1, not right - left. Write this on the whiteboard once and point at it.
Forcing a window onto a prefix-sum problem. When negatives appear and monotonicity dies, candidates keep patching and dig a deeper hole. Recognize the boundary and switch tools.
Not explaining the amortized O(n) argument. Even with correct code, if you cannot say why two nested-looking loops are linear, the interviewer wonders if you got lucky. Say "each pointer moves forward only, so total work is bounded by 2n."

8Your practice path#

Do them in this order. Each one adds exactly one new idea. Names only, go solve them.

Warm up (fixed size and basic variable):

Maximum Average Subarray I (LeetCode 643)
Best Time to Buy and Sell Stock (LeetCode 121)
Contains Duplicate II (LeetCode 219)

Core (build real fluency):

Longest Substring Without Repeating Characters (LeetCode 3)
Minimum Size Subarray Sum (LeetCode 209)
Max Consecutive Ones III (LeetCode 1004)
Fruit Into Baskets (LeetCode 904)
Permutation in String (LeetCode 567)

Stretch (the harder variants and tricks):

Longest Repeating Character Replacement (LeetCode 424)
Subarrays with K Different Integers (LeetCode 992, the atMost trick)
Minimum Window Substring (LeetCode 76)
Sliding Window Maximum (LeetCode 239, pairs the window with a deque)
Longest Substring with At Most K Distinct Characters (LeetCode 340)

If you can solve Minimum Window Substring and Subarrays with K Different Integers without peeking, you own this pattern.

Follow-ups the interviewer will ask (and your answers)

"Why is this O(n) if there is a loop inside a loop?"

Amortization. The left pointer only moves forward and never passes right, so across the entire run it advances at most n times total. The inner while therefore runs at most n times in total, not n times per step. Each element enters once and leaves at most once, so total work is bounded by 2n, which is O(n).

"Now count how many subarrays satisfy the constraint instead of the longest one."

Same window, different record step. Whenever the window ending at right is valid, it contributes right - left + 1 new subarrays (every start from left to right works), so I add that to a running total instead of taking a max. This only holds because the constraint is monotonic.

"The problem now says exactly K distinct, not at most K. How?"

exactly(K) = atMost(K) - atMost(K-1). Each atMost is a standard variable window counting subarrays. Subtracting removes the ones with fewer than K distinct, leaving exactly K. It is the clean way because an "exactly" constraint is not monotonic on its own.

"What if the array has negative numbers and you want sum equals K?"

Then it is not a sliding window. Growing the window can decrease the sum, so the shrink logic has no monotonic signal to act on. I switch to prefix sums plus a hash map of seen prefix sums, checking for prefix[j] - K at each step. That is LeetCode 560.

"How would you find the max in every fixed window of size K efficiently?"

A plain window does not give the max in O(1) because the max can leave the left edge. I pair the window with a monotonic deque that holds indices in decreasing value order: push on the right, pop smaller values off the back, drop indices that fall out of the window off the front. The front is always the window max. Still O(n) total. That is LeetCode 239.

9Where this shows up#

Sliding window is a staple of the phone screen and the first onsite coding round everywhere.
Amazon, Google, Meta, Microsoft, and the top startups all pull from this well, especially the string variants and the "longest or shortest with a constraint" framings.
It is popular precisely because it separates people who memorize solutions from people who understand incremental state, and it fits a 35-minute slot cleanly.
Expect at least one window-flavored question in most array and string rounds.

What you can now explain in the room

How to spot a window from the words "contiguous" plus "longest/shortest/at most K."
Both templates: fixed size (add one, drop one) and variable size (grow right, shrink left while invalid).
Why the pattern is O(n), using the amortized "each pointer moves forward only" argument.
Where to record the answer for longest versus shortest, and why mixing them causes off-by-one bugs.
The atMost subtraction trick for exactly-K problems and the right-minus-left-plus-one counting trick.
Why negatives plus a sum target kill monotonicity and push you to prefix sums instead.

Want to see exactly which companies and rounds lean on this pattern? Check the company guides to map it to your target.

← Previous

Shortest Paths: Dijkstra and Bellman-Ford

Stacks and the Monotonic Stack

Get a prep plan built around your Sliding Window interview

Tell us the role and your interview date. We will send back a dated, day by day plan. Free.

Thanks. Check your inbox, your Sliding Window prep plan is on the way.