Sliding window: how to spot it
We'll cover the following
Keep a range [L, R]. Move R to take in the next item. Move L when the range breaks a rule. Every item enters once and leaves once, so it is one pass instead of two nested loops.
How the question sounds
- Longest or shortest substring or subarray that satisfies a rule
- The word contiguous
- Fixed size k: max sum of 3 days, average of every 5 readings
- Variable size: no repeats, at most k distinct, sum at least target
The two shapes
Where it shows up in GenAI work
Rate limiters use a sliding window over recent requests. Splitting long documents into overlapping windows for embeddings, and trimming a conversation to fit a model's context window, are the same idea.
Is it sliding window?
Decide yes or no before you open each answer.
Check yourselfFind the longest substring with no repeating characters.
Yes. Contiguous and "longest" with a rule. Grow right, shrink left when a repeat appears.
Check yourselfFind the maximum sum of any 3 consecutive days of sales.
Yes. Fixed window of size 3. Add the new day, remove the old one.
Check yourselfGiven a sorted array, find two numbers that add up to a target.
No. The two numbers are not a contiguous range. This is two pointers from both ends.
Check yourselfFind the smallest subarray whose sum is at least 7 (all numbers positive).
Yes. Expand right until the sum is enough, then shrink left to make it short.
Check yourselfReturn the indices of two numbers in an unsorted array that add up to a target.
No. Pairs can be anywhere in the array. A hash map of seen values fits here.
Check yourselfCount how many islands are in a grid of land and water.
No. This is a grid search, so BFS or DFS, not a range moving along a line.
Problems in this pattern
- Maximum sum of k days · Easy · Fixed window
- Longest substring without repeats · Medium · Variable window
- Shortest subarray with sum at least target · Medium · Variable window
- Longest with at most k different letters · Medium · Variable window
- Longest run of ones with k flips · Medium · Variable window
Summary: say it in the interview
- Fixed window: Add the new item, remove the old one, compare. The length never changes.
- Variable window: Grow R until the rule breaks, then shrink L until it holds again. Track the best length.