Fixed Window Rate Limiter Bug — 2x Burst at Boundaries
A fixed-window rate limiter at 1,000 RPM allowed 10,000+ requests per user by timing at boundaries.
- Fixed window: constant size k. Add right, subtract left. O(n) total.
- Variable window: expand right freely, shrink left when constraint is violated.
- State tracking: HashMap, frequency counter, or running sum to maintain window state incrementally.
- Replaces O(n²) brute force with O(n) single-pass on streaming data, log analysis, and rate limiting.
- Each element enters and exits the window at most once — this is what makes it O(n).
- Forgetting Math.max on the left boundary in variable windows. Without it, the left pointer jumps backward when a duplicate was seen before the current window, silently producing wrong answers.
Subarray and substring problems dominate coding interviews and production systems alike. Finding the maximum sum of k consecutive elements, detecting rate limit violations in a time window, or identifying the longest substring without repeating characters — all of these share the same structure: a contiguous window of data that must be evaluated efficiently.
The naive approach checks every possible window from scratch — O(n²) or worse. Sliding window eliminates this by maintaining the window state incrementally. When the window slides one position to the right, you add the new element and remove the old one in O(1), rather than recomputing the entire window. This single insight converts O(n*k) brute force into O(n) single-pass.
Two flavors exist: fixed-size windows (constant k) and variable-size windows (expand/contract based on a constraint). Both share the invariant that each element enters and exits the window at most once. Recognizing which flavor applies — and correctly implementing the constraint logic — is the difference between a correct solution and a silent wrong answer.
Worked Example — Maximum Sum Subarray of Size K
Find the maximum sum subarray of size k=3 in arr=[2,1,5,1,3,2].
- Initialize: window_sum = sum(arr[0..2]) = 2+1+5 = 8. max_sum = 8.
- Slide right: i=3. Remove arr[0]=2, add arr[3]=1. window_sum = 8 - 2 + 1 = 7. max_sum stays 8.
- i=4: remove arr[1]=1, add arr[4]=3. window_sum = 7 - 1 + 3 = 9. max_sum = 9.
- i=5: remove arr[2]=5, add arr[5]=2. window_sum = 9 - 5 + 2 = 6. max_sum stays 9.
- Result: 9 (subarray [5,1,3]).
For variable-size windows (e.g., longest substring with at most k distinct chars): expand right pointer, and when the constraint is violated, shrink by advancing the left pointer until valid again. The window always contains a valid subarray. Each element enters and leaves the window at most once, giving O(n) time.
How Sliding Window Works — Plain English and Step-by-Step
A sliding window maintains a contiguous subarray or substring and slides it across the input to avoid O(n^2) brute force.
Fixed-size window (size k) — max sum subarray: 1. Compute sum of first k elements. 2. For each new position i from k to n-1: add arr[i], subtract arr[i-k]. Update max. O(n) total — each element is added and removed exactly once.
Variable-size window — longest substring without repeating characters: 1. Use left and right pointers, both starting at 0. Maintain a seen dict of last index. 2. Expand right: for each char, if it was seen at index >= left, move left to seen[char]+1. 3. Update seen[char] = right. Record window length right-left+1 if it's a new maximum.
Worked example — fixed window k=3, arr=[2,1,5,1,3,2], find max sum: Window [2,1,5]: sum=8, max=8. Slide: -2+1=7. Window [1,5,1]: sum=7. max=8. Slide: -1+3=9. Window [5,1,3]: sum=9. max=9. Slide: -5+2=6. Window [1,3,2]: sum=6. max=9. Answer: 9.
Fixed Window — Maximum Sum Subarray of Size K
The fixed-size window, 1, 3, 2}; maintains a running sum. After the initial window is computed, each subsequent step adds the new right element and removes the element that left the window — both in O(1). This achieves O(n) overall versus O(n*k) brute force. The same pattern applies to maximum/minimum, average, or any aggregation over a window of fixed size.
Variable Window — Longest Substring Without Repeating Characters
The variable window expands the right pointer unconditionally and shrinks the left pointer only when the constraint is violated. A hash map tracks the last seen index of each character. When a duplicate is encountered, move left to max(left, last_seen[char]+1) to skip past it — the max ensures left never moves backward. Update last_seen[char] after the left adjustment.
Variable Window — At Most K Distinct Characters
The variable window expands the right pointer unconditionally and shrinks the left pointer only when the constraint is violated. A frequency map tracks the count of each character in the window. When the number of distinct characters exceeds k, shrink from the left by decrementing the left character's frequency and removing it from the map when the count reaches 0.
Sliding Window Minimum — The Monotonic Deque Pattern
Finding the maximum or minimum of every window of size k is a classic problem. The naive approach scans all k elements in each window — O(n*k). A monotonic deque maintains candidates in sorted order, giving O(1) amortized per slide.
For maximum: maintain a deque of indices where values are in decreasing order. The front of the deque is always the maximum of the current window. When sliding, remove the front if it's outside the window, and remove all elements from the back that are smaller than the new element (they can never be the maximum while the new element is in the window).
| Aspect | Fixed-Size Window | Variable-Size Window | Monotonic Deque Window |
|---|---|---|---|
| Window size | Constant k | Determined by constraint | Constant k |
| Pointer movement | Right advances, left follows at distance k | Right advances, left advances when constraint violated | Right advances, left follows at distance k |
| State tracking | Running sum or aggregate | HashMap / frequency map | Deque of indices in sorted order |
| Time complexity | O(n) | O(n) | O(n) amortized |
| Space complexity | O(1) | O(k) — constraint size | O(k) — window size |
| Best for | Max/min/avg sum of size k | Longest/shortest substring with constraint | Max/min in every window of size k |
| Constraint type | None — size is the constraint | Monotone (at most k, sum <= target) | None — size is the constraint |
| Classic problems | Max sum subarray of size k, moving average | Longest substring without repeating, min window substring | Sliding window maximum, sliding window median |
| Key edge case | k > array length | Math.max on left boundary | Deque front outside window |
Key Takeaways
- Sliding window converts O(n*k) brute force to O(n) by incrementally updating the window. Each element enters and exits at most once.
- Fixed window: add right element, remove left element at each step. The speedup factor is k.
- Variable window: expand right freely, shrink left when the constraint is violated. Math.max on the left boundary is mandatory.
- Use a HashMap or frequency counter to track window state for string problems. Delete entries when count reaches 0.
- Recognise the pattern: any 'contiguous subarray/substring' problem with an optimization goal is a sliding window candidate.
- Sliding window requires a monotone constraint. Non-monotone constraints (exactly k) need the atMost(k) - atMost(k-1) trick.
- Monotonic deque maintains the window's max/min in O(1) amortized. Use it for 'max of every window of size k'.
- Always test variable windows with repeated elements ('abba', 'tmmzuxt') to catch the Math.max bug.
Interview Questions on This Topic
- QWhat is the time complexity of the sliding window technique and why? Prove that each element is visited at most twice.
- QGiven an array and integer k, find the maximum sum of any contiguous subarray of size k. What is the brute force complexity and how does sliding window improve it?
- QFind the length of the longest substring without repeating characters. What edge case does Math.max on the left boundary handle?
- QHow would you find the longest substring with exactly k distinct characters? Why can't you use sliding window directly, and what trick do you use?
- QExplain the monotonic deque pattern for sliding window maximum. Why is it O(n) amortized?
- QGiven an array of integers and a target sum, find the length of the shortest subarray with sum >= target. How does the variable window pattern apply here?
- QHow would you implement a sliding window rate limiter that enforces exactly N requests per minute without boundary burst exploits?
- QWhat is the difference between sliding window and two pointers? When would you choose one over the other?
- QGiven a string s and a string t, find the minimum window in s that contains all characters of t. What state do you maintain and how do you know when the window is valid?
- QHow would you find the median of every window of size k in O(n log k) time? What data structures would you use?
Frequently Asked Questions
How do I know when to use the sliding window technique?
Look for these signals in the problem: 'contiguous subarray or substring', 'maximum/minimum/longest/shortest', and a constraint on the window (size k, at most k distinct elements, sum <= target). If you would naturally write a nested loop, a sliding window is likely the optimization.
What is the difference between sliding window and two pointers?
Two pointers usually work on a sorted array from both ends (one at left, one at right) and meet in the middle — used for pair sum problems. Sliding window has both pointers moving in the same direction with the left pointer always behind the right. Sliding window is a subset of two pointers where both move in the same direction.
What is the difference between fixed and variable sliding window?
Fixed window has constant size k — slide by adding the new right element and removing the old left element in O(1). Variable window has a size determined by a constraint — expand right freely, shrink left when the constraint is violated. Both achieve O(n).
When does the sliding window technique not apply?
Sliding window requires a monotone constraint: adding elements makes the window 'more invalid', removing makes it 'more valid'. If the constraint is non-monotone (e.g., exactly k distinct characters, not at most k), you need a different approach such as the 'at most k' minus 'at most k-1' trick.
How do I know if a problem is a sliding window problem?
Look for: subarray/substring of size k, longest/shortest subarray satisfying a condition, max/min in consecutive windows. If the problem asks about a contiguous range of elements and the answer changes incrementally as you add/remove one element, sliding window applies.
What is the difference between fixed-size and variable-size sliding windows?
Fixed-size: window length is always k; you add the new right element and remove the leftmost element each step. Variable-size: you expand right greedily and only shrink left when a constraint (e.g., too many distinct chars) is violated. Variable windows track conditions like a hash map of character counts.
Why is the sliding window O(n) even with a nested while loop?
The left pointer only moves forward, never backward. Each element is visited at most twice: once when the right pointer passes it, and once when the left pointer passes it. Total operations: at most 2n, which is O(n). The nested while loop does not create O(n²) because the left pointer's total movement across all iterations is bounded by n.
How do I solve 'exactly k distinct characters' with sliding window?
Use the atMost(k) - atMost(k-1) trick. Compute the number of substrings with at most k distinct characters, then subtract the number with at most k-1. Both sub-problems use monotone constraints and work with sliding window. The result isolates exactly k distinct.
That's Arrays & Strings. Mark it forged?
3 min read · try the examples if you haven't