Sliding Window
Most people know the sliding window trick. Very few know when to stop sliding and start shrinking.
Sliding Window is one of those patterns that looks simple until you hit a variable window problem in an interview and freeze. The fixed window variant is mechanical. The variable window variant requires you to maintain an invariant under pressure. That’s where interviews are won and lost.
This post covers both. By the end you’ll know exactly which variant a problem is asking for before you write a single line of code.
The Core Insight
“A nested loop recomputes everything from scratch. Sliding Window carries the result forward — adding one element on the right, dropping one on the left. The window doesn’t restart. It remembers.”
The Two Flavors
Flavor 1 — Fixed Size Window
[ · · [ 4 1 7 ] 3 · · ]
↑ ↑
drop addWindow size k is given. Slide one step at a time — drop the leftmost element, add the new right element, maintain a running computation. Never recompute from scratch.
Best for: maximum sum of k elements, average of every window, first negative in every window
Flavor 2 — Variable Size Window
[ · [ L 3 2 6 R ] · ]
↑ ↑
shrink expandNo fixed size. Expand right until the window violates the condition, then shrink from the left until it’s valid again. The window breathes — it grows and contracts based on what’s inside it.
Best for: longest substring with condition, smallest subarray with sum ≥ k, minimum window substring
Why Each Flavor Works
Fixed window works because adding and dropping one element at a time is O(1). Instead of summing k elements fresh every step — O(n·k) total — you maintain a running value and update it in constant time. One addition, one subtraction, done.
Variable window works because of the monotonic shrink property. On an array of positive numbers, if the window sum exceeds the target, removing the leftmost element always decreases the sum. That directionality is what lets you shrink confidently without missing valid windows.
With negative numbers this property breaks — removing an element might increase the sum. The window has no direction. That’s why variable window only works reliably on non-negative values for sum-based problems.
Pattern Fingerprint — How to Identify It Instantly
Fixed window — look for: “subarray of size k” · “maximum average of k elements” · “sum of every window of size k” · “first negative in every window” · k is explicitly given in the problem
Variable window — look for: “longest substring” + any condition · “smallest subarray with sum ≥ k” · “at most k distinct characters” · “no repeating characters” · “minimum window containing all characters” · “fruit into baskets” · longest / shortest + contiguous + condition
Decoys to reject immediately: subarray sum = k with negative numbers → Prefix Sum + HashMap · non-contiguous subsets → DP or Greedy · sorted array + pair condition → Two Pointers · “count of subarrays” with complex conditions → Prefix Sum
The single question that separates Sliding Window from everything else: Is the data contiguous AND does shrinking from the left always move me toward a valid state? Both must be yes.
The Problems — All 10 with Most Asked Highlighted
Problems marked with ★ appear repeatedly across Google, Meta, Amazon, Flipkart, and Swiggy interview reports.
Fixed window (5 problems):
Maximum Average Subarray I — the cleanest fixed window starter. Running sum, slide, track max.
Maximum Sum of Distinct Subarrays With Length K — fixed window + HashSet to enforce distinct constraint.
Contains Duplicate II — fixed window of size k + HashSet. Good for building the window + set pattern.
Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold — count windows satisfying a condition. Clean fixed window practice.
★ Sliding Window Maximum — hardest fixed window problem. Requires a monotonic deque inside the window. Asked at Google, Amazon. Interviewers test whether you can optimize beyond the naive O(n·k) approach.
Variable window (5 problems):
★ Longest Substring Without Repeating Characters — the canonical variable window problem. Asked at every tier-1 company. Interviewers test your window shrink logic and HashMap vs array tradeoff.
★ Minimum Window Substring — hardest in the set. Expand to include all required characters, shrink as far as possible. Asked at Google, Meta, Amazon. Two-pointer HashMap with a have/need counter is the expected approach.
★ Longest Repeating Character Replacement — frequency map + window validity trick. The invariant is
window size - max frequency ≤ k. Asked at Google, Meta. Interviewers test whether you understand why you don’t need to decrease maxFreq when shrinking.Fruit Into Baskets — disguised “at most 2 distinct types” problem. Don’t let the story confuse you — map it directly to longest subarray with at most k distinct values.
Longest Substring with At Most K Distinct Characters — generalized version of Fruit Into Baskets. HashMap frequency window. k=2 gives you the fruit problem.
The Two Skeletons
Fixed window:
// build first window
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i];
int maxSum = windowSum;
// slide: add right, drop left — O(1) per step
for (int i = k; i < nums.length; i++) {
windowSum += nums[i] - nums[i - k];
maxSum = Math.max(maxSum, windowSum);
}Variable window:
int left = 0;
int maxLen = 0;
Map<Character, Integer> freq = new HashMap<>();
for (int right = 0; right < s.length(); right++) {
// expand: add right character to window
freq.merge(s.charAt(right), 1, Integer::sum);
// shrink: contract from left until window is valid again
while (isInvalid(freq)) {
freq.merge(s.charAt(left), -1, Integer::sum);
if (freq.get(s.charAt(left)) == 0)
freq.remove(s.charAt(left));
left++;
}
// window is now valid — update answer
maxLen = Math.max(maxLen, right - left + 1);
}The variable window invariant to maintain at all times: after the while loop, the window from left to right is always valid. The answer is updated only in this valid state.
The Decision Guide
1. Does the problem involve a contiguous subarray or substring?
No → not Sliding Window
2. Is the window size k given explicitly in the problem?
Yes → Fixed window
3. Does the problem ask for longest or shortest subarray satisfying a condition? Yes → Variable window
4. Are all values non-negative for sum-based problems?
No → Prefix Sum + HashMap instead
5. Does shrinking from the left always move toward a valid state?
Yes → Variable window confirmed
6. Is the array sorted and are you finding a pair with a sum condition?
Yes → Two Pointers instead
The Interviewer’s Playbook — Questions They Will Ask You
On fixed window:
“Why is the fixed window O(n) and not O(n·k)?”
Because you never recompute the window from scratch. Each step is one addition and one subtraction — constant time. Across n steps that’s O(n) total regardless of k.“In Sliding Window Maximum, why do you need a deque and not just a max variable?”
A max variable breaks when the current maximum leaves the window — you have no way to know the new maximum without scanning the whole window again. A monotonic deque maintains candidates in decreasing order so the front is always the current maximum, and stale candidates are evicted from the back as you add and from the front as they go out of range.
On variable window:
“Why does the variable window only work reliably with non-negative numbers for sum problems?”
With non-negative numbers, adding an element never decreases the sum and removing one never increases it. That monotonic behavior is what makes shrinking from the left meaningful — you know removing an element moves you toward a smaller sum. With negatives, removing an element might increase the sum and you lose that guarantee.“In Longest Repeating Character Replacement, why don’t you decrease maxFreq when shrinking the window?”
Because you’re looking for the longest valid window. The answer can only improve if maxFreq increases. If the current window shrinks and maxFreq would decrease, that window is smaller than your current best — you don’t care about it. You only update maxFreq upward, never downward.“What’s the difference between Sliding Window and Two Pointers?”
Two Pointers works on sorted arrays where converging from opposite ends exploits a monotonic sum property. Sliding Window works on unsorted data where a contiguous window expands and contracts in one direction. If you sorted the array to make it work — it’s probably Two Pointers. If the order is preserved — it’s probably Sliding Window.“Can you solve Minimum Window Substring without a HashMap?”
You could use a frequency array of size 128 (ASCII) instead — O(1) space vs O(k) for HashMap where k is the charset size. In practice both are considered O(1) for fixed charset sizes. The array approach has better constant factors.
Before You Move On — Things That Will Bite You
Variable window on negative numbers for sum problems is wrong. The shrink logic breaks. Use Prefix Sum + HashMap instead.
The window size formula is
right - left + 1, notright - left. Off by one here costs you the answer on every variable window problem.Build the first window before the slide loop on fixed window problems. Don’t try to handle the first window inside the main loop — it adds unnecessary branching.
In variable window, update the answer after the while loop, not inside it. The answer is only valid when the window satisfies the condition — that’s after shrinking, not during.
Don’t confuse “at most k distinct” with “exactly k distinct”. Exactly k = (at most k) minus (at most k-1). This is a common follow-up interviewers use to test depth.
Sliding Window Maximum is not a standard sliding window. It needs a monotonic deque. Don’t try to solve it with just a max variable — you’ll get O(n·k) and likely TLE.
Fruit Into Baskets is just “at most 2 distinct values”. Strip the story, identify the constraint, apply the template. Interviewers use disguised problems to test whether you see through the narrative.
The One Thing to Remember
“Is the data contiguous AND does shrinking from the left always move me toward a valid state?”
If both are yes — Sliding Window. Fixed if k is given. Variable if you’re optimizing length.
If the array has negatives and you’re doing sum-based work — stop. The shrink logic has no direction. Use Prefix Sum + HashMap.
— Nitin Singh, Level Up Your Programming with Nitin
Subscribe to get the next post in your inbox.
Hashnode | Substack | LinkedIn | Youtube | Instagram | GIT | Topmate