Sliding Window Interview Problems — Patterns, Code and Gotchas
Sliding window problems show up in almost every technical interview at top-tier companies — not because they're obscure, but because they test whether you think algorithmically or just mechanically. The naive solution to most array and string problems is O(n²) nested loops. The sliding window technique collapses that to O(n), and interviewers use these problems specifically to see if you can make that leap without prompting.
The core problem it solves is this: any time you need to examine a contiguous subarray or substring under some constraint — maximum sum, longest without repeating characters, smallest with a target sum — you're repeatedly looking at overlapping data. Brute force recalculates that overlapping data every single iteration. A sliding window maintains just enough state so you only ever process each element once as the window expands and once as it contracts.
By the end of this article you'll be able to recognise which of the two main window types (fixed-size vs dynamic) applies to a given problem, implement both from memory, handle the edge cases that trip up even experienced candidates, and answer the follow-up questions interviewers use to separate good solutions from great ones.
Fixed-Size Windows — When the Frame Never Changes
A fixed-size window is the simpler of the two patterns. The window length is given to you upfront and never changes — your only job is to slide it across the array one step at a time and track whatever metric you care about.
The key insight is how you update the window in O(1) instead of O(k): when the window moves one position to the right, exactly one element leaves the left edge and one enters the right edge. That means you don't need to sum (or hash, or count) the whole window again — you just subtract the outgoing element and add the incoming one.
This pattern covers problems like: maximum average subarray of length k, maximum sum subarray of length k, count of anagram occurrences in a string, and find all substrings containing exactly k distinct characters with a fixed length.
The implementation template is always the same: build the first window, record your answer, then loop from index k to n-1, sliding by one each iteration. Get that template into muscle memory and the code almost writes itself.
public class MaxSumFixedWindow { /** * Finds the maximum sum of any contiguous subarray of exactly 'windowSize' elements. * Time: O(n) — each element is added once and removed once * Space: O(1) — no extra data structures needed */ public static int findMaxSum(int[] prices, int windowSize) { int totalElements = prices.length; // Edge case: window is larger than the array itself if (windowSize > totalElements) { throw new IllegalArgumentException( "Window size " + windowSize + " exceeds array length " + totalElements ); } // Step 1: Build the first window by summing the first 'windowSize' elements int currentWindowSum = 0; for (int i = 0; i < windowSize; i++) { currentWindowSum += prices[i]; } // The first window is our baseline best answer int maxSum = currentWindowSum; // Step 2: Slide the window one position at a time across the rest of the array for (int rightEdge = windowSize; rightEdge < totalElements; rightEdge++) { int leftEdge = rightEdge - windowSize; // the element we're dropping off the left // Drop the outgoing element, add the incoming element — one operation each currentWindowSum += prices[rightEdge]; // new element entering from the right currentWindowSum -= prices[leftEdge]; // old element leaving from the left // Update our best answer if this window beats it if (currentWindowSum > maxSum) { maxSum = currentWindowSum; } } return maxSum; } public static void main(String[] args) { // Simulating daily stock prices over two weeks int[] dailyStockPrices = {12, 5, 35, 8, 6, 14, 21, 9, 3, 18, 27, 11, 4, 16}; int targetWindowDays = 4; int result = findMaxSum(dailyStockPrices, targetWindowDays); System.out.println("Stock prices: " + java.util.Arrays.toString(dailyStockPrices)); System.out.println("Window size (days): " + targetWindowDays); System.out.println("Max 4-day sum: " + result); // The window [18, 27, 11, 4] isn't it — let's think: [14, 21, 9, 3] = 47 // [21, 9, 3, 18] = 51, [9, 3, 18, 27] = 57 — yes, 57 wins System.out.println("Winning window: [9, 3, 18, 27] = 57"); } }
Window size (days): 4
Max 4-day sum: 57
Winning window: [9, 3, 18, 27] = 57
Dynamic Windows — When the Frame Grows and Shrinks Based on a Condition
Dynamic (or variable-size) windows are where most candidates stumble, because the window doesn't have a fixed length — it grows until it violates a constraint, then shrinks from the left until it's valid again. The two-pointer approach drives this: a right pointer expands the window, and a left pointer contracts it.
The mental model that makes this click: think of the right pointer as greedy and optimistic — it keeps consuming elements hoping to satisfy or maximise the target. The left pointer is the enforcer — when the window breaks the rules, it evicts elements from the left until the window is valid again.
This pattern handles: longest substring without repeating characters, minimum size subarray with sum ≥ target, longest subarray with at most k distinct characters, and fruit into baskets (same idea, different flavour).
The critical implementation detail is the order of operations inside the loop: expand right first, update your state, then shrink left in a while loop until valid, then record your answer. Get that order wrong and you'll record invalid states or miss valid ones — a bug that's devilishly hard to spot under interview pressure.
import java.util.HashMap; import java.util.Map; public class LongestSubstringKDistinct { /** * Finds the length of the longest substring with at most 'maxDistinct' distinct characters. * Classic dynamic sliding window — the window expands greedily and contracts when violated. * Time: O(n) — right pointer visits each character once; left pointer also moves at most n times total * Space: O(k) — the frequency map holds at most maxDistinct + 1 entries at any moment */ public static int findLongest(String text, int maxDistinct) { if (text == null || text.isEmpty() || maxDistinct == 0) return 0; // Tracks how many times each character appears inside the current window Map<Character, Integer> charFrequencyInWindow = new HashMap<>(); int leftPointer = 0; // left edge of the window (contracts when rule is broken) int longestFound = 0; // best valid window length seen so far // rightPointer is the right edge — it drives expansion of the window for (int rightPointer = 0; rightPointer < text.length(); rightPointer++) { char incomingChar = text.charAt(rightPointer); // Add the new character to our frequency map (window just expanded rightward) charFrequencyInWindow.put( incomingChar, charFrequencyInWindow.getOrDefault(incomingChar, 0) + 1 ); // The window is now INVALID — too many distinct characters // Shrink from the left until we're back to maxDistinct distinct chars while (charFrequencyInWindow.size() > maxDistinct) { char outgoingChar = text.charAt(leftPointer); // Reduce the frequency of the character we're evicting charFrequencyInWindow.put( outgoingChar, charFrequencyInWindow.get(outgoingChar) - 1 ); // If that character's count hit zero, remove it entirely // This is what keeps charFrequencyInWindow.size() accurate if (charFrequencyInWindow.get(outgoingChar) == 0) { charFrequencyInWindow.remove(outgoingChar); } leftPointer++; // shrink the window from the left } // Window is now valid — calculate its length and update best answer int currentWindowLength = rightPointer - leftPointer + 1; longestFound = Math.max(longestFound, currentWindowLength); } return longestFound; } public static void main(String[] args) { String dnaSequence = "AABABCBCBAABC"; int allowedDistinctBases = 2; int result = findLongest(dnaSequence, allowedDistinctBases); System.out.println("DNA sequence: " + dnaSequence); System.out.println("Max distinct bases: " + allowedDistinctBases); System.out.println("Longest valid substring length: " + result); // "BCBCB" has length 5 with only B and C — that's the answer System.out.println("Example valid window: \"BCBCB\" (length 5, distinct: B, C)"); // Test with a simpler case to verify System.out.println(); System.out.println("--- Edge case: maxDistinct = 1 ---"); String simpleText = "AAABBB"; System.out.println("Input: \"" + simpleText + "\", maxDistinct=1"); System.out.println("Result: " + findLongest(simpleText, 1)); // expects 3 (AAA or BBB) } }
Max distinct bases: 2
Longest valid substring length: 5
Example valid window: "BCBCB" (length 5, distinct: B, C)
--- Edge case: maxDistinct = 1 ---
Input: "AAABBB", maxDistinct=1
Result: 3
Recognising the Pattern Fast — The 3-Question Decision Framework
The hardest part of sliding window problems in an interview isn't the code — it's recognising within 60 seconds that sliding window is even the right tool. Interviewers watch this recognition moment closely.
Three questions will get you there every time. First: does the problem involve a contiguous subarray or substring? If the order doesn't matter or elements don't need to be adjacent, sliding window is the wrong tool — reach for a hash map or a sort instead. Second: is there a constraint on the window (sum ≥ target, at most k distinct, no repeating characters)? That constraint is what drives the window's expansion and contraction logic. Third: are you optimising for a minimum or maximum (shortest, longest, smallest, largest)? This tells you whether to update your answer after expanding (maximum) or after contracting (minimum).
For minimum problems — like smallest subarray with sum ≥ target — the trick is you shrink the window as aggressively as possible while still meeting the constraint, updating your best answer after each contraction, not after expansion.
public class MinSizeSubarraySum { /** * Finds the minimum length of a contiguous subarray whose sum is >= targetSum. * Returns Integer.MAX_VALUE if no such subarray exists. * * Key difference from max-length problems: we update the answer INSIDE the shrink loop, * not after it — because we want the smallest valid window, so we record it the moment * it becomes valid and keep trying to make it even smaller. * * Time: O(n) — each element touched at most twice (once by right, once by left) * Space: O(1) */ public static int minSubarrayLength(int[] bandwidthReadings, int targetSum) { int leftPointer = 0; int currentWindowSum = 0; int minimumLength = Integer.MAX_VALUE; // start pessimistically — no valid window found yet for (int rightPointer = 0; rightPointer < bandwidthReadings.length; rightPointer++) { // Expand: absorb the next reading into the window currentWindowSum += bandwidthReadings[rightPointer]; // Shrink: as long as the window sum meets our target, try to make the window smaller // We update the answer INSIDE this loop — that's the minimum-problem pattern while (currentWindowSum >= targetSum) { int currentWindowLength = rightPointer - leftPointer + 1; // This window is valid — is it smaller than our current best? minimumLength = Math.min(minimumLength, currentWindowLength); // Try shrinking further — evict the leftmost element currentWindowSum -= bandwidthReadings[leftPointer]; leftPointer++; } } // If minimumLength never changed, no valid subarray existed return (minimumLength == Integer.MAX_VALUE) ? 0 : minimumLength; } public static void main(String[] args) { // Network bandwidth readings (Mbps) — find the shortest burst that totals >= 51 Mbps int[] bandwidthReadings = {2, 3, 1, 2, 4, 3, 8, 12, 5, 6}; int targetBandwidth = 51; int result = minSubarrayLength(bandwidthReadings, targetBandwidth); System.out.println("Bandwidth readings: " + java.util.Arrays.toString(bandwidthReadings)); System.out.println("Target sum: " + targetBandwidth); System.out.println("Minimum subarray length: " + result); // Verify with a classic LeetCode-style test case int[] classicInput = {2, 3, 1, 2, 4, 3}; int classicTarget = 7; System.out.println(); System.out.println("Classic test — array: " + java.util.Arrays.toString(classicInput)); System.out.println("Target: " + classicTarget); System.out.println("Result: " + minSubarrayLength(classicInput, classicTarget)); // [4, 3] has sum 7 and length 2 — that's the minimum } }
Target sum: 51
Minimum subarray length: 7
Classic test — array: [2, 3, 1, 2, 4, 3]
Target: 7
Result: 2
| Aspect | Fixed-Size Window | Dynamic Window |
|---|---|---|
| Window size | Given as input — constant throughout | Determined by a constraint — varies per iteration |
| Pointers needed | One pointer (or index + offset) | Two explicit pointers (left and right) |
| Shrink logic | Automatic — always drops element at index (right - k) | Conditional — while loop runs until constraint satisfied |
| Answer update timing | After every slide (every iteration) | Max problems: after shrink. Min problems: inside shrink loop |
| State tracking | Simple running total or counter | Usually a HashMap or frequency array for the window's contents |
| Typical problem signal | 'subarray of length k' is in the problem statement | 'longest', 'shortest', 'at most k', 'no repeating' — flexible length |
| Example problems | Max sum of k elements, count anagrams | Longest substring without repeats, min subarray sum >= target |
| Time complexity | O(n) | O(n) — left pointer moves at most n times total across all iterations |
🎯 Key Takeaways
- The subtract-and-add update is the entire reason sliding window is O(n) instead of O(n×k) — without it you're just doing brute force with extra steps
- Use while to shrink, never if — an if only evicts one element per expansion, but the window may need to contract multiple positions before it's valid again
- Maximum-length problems update the answer after the shrink phase; minimum-length problems update inside the shrink loop — mix these up and you'll get off-by-one errors that are very hard to debug under pressure
- The 3-question check (contiguous? constrained? optimising min or max?) lets you identify a sliding window problem in under 30 seconds — interviewers notice when you name the pattern before touching the keyboard
⚠ Common Mistakes to Avoid
- ✕Mistake 1: Using if instead of while to shrink the dynamic window — Symptom: the algorithm records incorrect (invalid) window states and returns a wrong answer that passes most test cases but fails on inputs where multiple shrink steps are needed in one iteration — Fix: always use while (condition is violated) { shrink left; leftPointer++; } — the while loop keeps contracting until the window is genuinely valid, not just one step less violated
- ✕Mistake 2: Forgetting to remove a character from the HashMap when its frequency hits zero — Symptom: charFrequencyInWindow.size() keeps growing even when characters have left the window, so the 'distinct count' constraint is never satisfied and the left pointer races to the end of the string — Fix: after decrementing a character's count, immediately check if (count == 0) { map.remove(character); } — the size() of the map is your distinct-character counter, and it only stays accurate if you clean up zero-count entries
- ✕Mistake 3: Initialising minimumLength as 0 instead of Integer.MAX_VALUE for minimum-size problems — Symptom: the function returns 0 even when a valid subarray exists, because 0 is always less than any real window length so Math.min() never updates it — Fix: always initialise to Integer.MAX_VALUE (pessimistic start), then at the end return (minimumLength == Integer.MAX_VALUE) ? 0 : minimumLength — the 0 return only happens when no valid window was ever found, which is the correct semantics
Interview Questions on This Topic
- QGiven a string and integer k, find the length of the longest substring that contains at most k distinct characters. Walk me through your approach before writing any code — how do you decide between a fixed and dynamic window here?
- QYour sliding window solution runs in O(n) time. Can you explain specifically WHY each element is processed at most twice — and would your solution still be O(n) if the inner while loop ran many times on the same iteration?
- QHow would you modify your dynamic window solution if the constraint changed from 'at most k distinct' to 'exactly k distinct'? What's the minimal code change needed, and is there a clever one-line trick?
Frequently Asked Questions
What is the difference between a sliding window and two pointers?
Two pointers is the broader technique — it describes any algorithm using two indices that move through a data structure. Sliding window is a specific application of two pointers where the two indices define the edges of a contiguous subarray or substring and move in the same direction (both left to right). All sliding windows use two pointers, but not all two-pointer problems are sliding windows.
When should I use a sliding window versus a prefix sum array?
Use a sliding window when you need to find an optimal window (longest, shortest, maximum, minimum) under a dynamic constraint that changes as you scan — especially when the constraint depends on the content of the window, like distinct characters or no repeats. Use a prefix sum when you need to answer multiple arbitrary range-sum queries on a fixed array, since prefix sums let each query run in O(1) after O(n) preprocessing.
Why does my sliding window give wrong answers on arrays with negative numbers?
The standard dynamic sliding window assumes that adding more elements to the window can only make the sum larger (or at worst neutral), so you can always meaningfully expand right and contract left. Negative numbers break this assumption — shrinking the window might actually increase the sum, meaning the greedy expand-then-contract logic no longer guarantees you've found the optimal window. For arrays with negatives, Kadane's algorithm or a deque-based approach is usually the right tool instead.
Written and reviewed by senior developers with real-world experience across enterprise, startup and open-source projects. Every article on TheCodeForge is written to be clear, accurate and genuinely useful — not just SEO filler.