Sliding window interview questions

A sliding window turns questions about contiguous subarrays and substrings from quadratic to linear by reusing the work from the previous position instead of starting over.

How do I solve sliding window interview questions?

A sliding window keeps a contiguous range of the input between two indexes, expanding the right end and shrinking the left while a condition is broken or satisfied. It answers longest, shortest or best-subarray and substring questions in linear time because each element enters and leaves the window once.

Practise sliding window

How to recognise a sliding window problem

The question is about a contiguous subarray or substring: longest, shortest, maximum sum, at most k distinct, containing all of some characters.

A brute force would examine every start and end, recomputing a sum or a count each time.

Adding an element and removing an element each change the answer in a way you can update cheaply.

How to build the solution

Decide what to track about the window: a running sum, a count of each character, the number of distinct items.

Expand the right end one element at a time and add it to the tracked state.

While the window is invalid (or, for shortest-window problems, while it is valid), advance the left end and remove that element from the state.

Update the best answer at the right moment: after shrinking for longest-valid windows, before shrinking for shortest-valid windows.

Classic problems to practise

Best Time to Buy and Sell Stock, Longest Substring Without Repeating Characters, Longest Repeating Character Replacement, Permutation in String, Minimum Window Substring, Maximum Average Subarray, Sliding Window Maximum.

Mistakes interviewers see

Updating the answer at the wrong moment, so the window recorded is one that was invalid.

Forgetting to remove the left element's contribution from the counts or the sum when you shrink.

Using a window on data with negative numbers when the shrink rule assumes values only increase the sum. Prefix sums and a hash map are the fix.

Rebuilding the window's state from scratch each step, which silently brings the quadratic time back.

Practise it as an interview

Take a topic-based interview on sliding window to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.

Frequently asked questions

What is the time complexity of a sliding window?

Usually linear. The right pointer visits each element once and the left pointer visits each element at most once, even though there is a loop inside a loop.

Fixed or variable window?

Use a fixed window when the length is given, such as the best average of k elements. Use a variable window when the length is what you are optimising or constraining.