Sliding Window

Question 1

What is the main benefit of Sliding Window over a naive nested loop?

Accepted Answer

O(n) by reusing the previous window sum — Sliding window avoids re-calculating the sum of overlapping elements, providing a linear time solution.

Question 2

The sliding-window technique reduces many subarray/substring problems from O(n²) to O(n) by…

Accepted Answer

By reusing the previous window's work — Instead of recomputing an aggregate for every subarray, you slide the window: add the entering element and remove the leaving one in O(1), so the whole pass is O(n).

Question 3

What distinguishes a FIXED-size sliding window from a VARIABLE-size one?

Accepted Answer

Fixed size k stays constant; variable size adapts to a constraint — Fixed windows (e.g. max sum of k consecutive elements) keep width k. Variable windows expand the right edge and contract the left until a constraint (sum, distinct count) is satisfied.

Question 4

For 'maximum sum of a subarray of size k', the window update on each slide is…

Accepted Answer

Add right, subtract left, advance — Add the new right element and subtract the element leaving on the left — O(1) per slide — tracking the running max. Total O(n).

Question 5

In 'longest substring without repeating characters', when a duplicate enters, you…

Accepted Answer

Shrink from the left until the duplicate leaves the window — Advance the left edge (often jumping via a last-seen index map) until the repeated character is excluded, keeping the window valid, then continue expanding the right edge.

Question 6

What auxiliary structure commonly supports a variable-size window over characters?

Accepted Answer

A hash map of frequencies — A frequency map records counts of items currently inside the window, letting you test the constraint (e.g. all-distinct, contains-target-counts) in O(1) as the window changes.

Question 7

The sliding-window pattern is fundamentally a special case of which other technique?

Accepted Answer

Two pointers, same direction — Both window edges are pointers advancing in the same direction; the window is the range between them. Sliding window = two pointers + maintained window state.

Question 8

Sliding window over a sum constraint can break when the array contains negative numbers because…

Accepted Answer

Adding elements can decrease the sum when negatives are present — The shrink/expand logic assumes adding elements only grows the metric monotonically. Negatives break that monotonicity; such problems often need prefix sums + a hash map instead.

Question 9

For 'minimum window substring' (smallest window of S containing all chars of T), you…

Accepted Answer

Expand until valid, then contract to minimize it — Grow the right edge until the window covers T, then shrink the left edge as far as possible while coverage holds, recording the minimum. Each character enters and leaves at most once: O(n).

Question 10

'Longest substring with at most K distinct characters' contracts the window when…

Accepted Answer

Distinct character count exceeds K — Track distinct-count via a frequency map; whenever distinct > K, advance left (decrementing counts, dropping a key at zero) until distinct ≤ K again.

Sliding Window: Max Sum Subarray

Maximum sum of k elements

Test your knowledge

What is the main benefit of Sliding Window over a naive nested loop?

Write the code

Max Sum Subarray of Size K

Example Cases

The short version

In more depth

Sliding Window

The idea

Two forms

Recognising it

When to reach for this

Interview Questions

References & Further Reading

Love this visualization?