The Sliding Window Algorithm Inside Your Rate Limiter
Related service: Mock interviews
The sliding window algorithm is 3 moves. Shrink from the left while a rule is broken. Grow on the right. Check the answer.
The algorithm comes in 2 shapes, fixed size and variable size. It is legal only when the condition is monotonic in window size.
On this page
A sliding window rate limiter runs the same algorithm.
An API gateway allowing 100 requests a minute per key can run it.
LeetCode calls the same pattern “longest substring without repeating characters”.
How the sliding window algorithm works in production
A gateway holds, per key, the requests inside the last 60 seconds.
A new request at time t drops everything older than t minus 60. It adds t at the back, and rejects if the count is over.
from collections import deque
class RateLimiter:
def __init__(self, limit, window):
self.limit, self.window = limit, window
self.hits = {}
def allow(self, key, now):
q = self.hits.setdefault(key, deque())
while q and q[0] <= now - self.window:
q.popleft()
if len(q) >= self.limit:
return False
q.append(now)
return TrueThe rule here is age. In interview problems it is a count, a sum or a set membership. The shape does not change.
Shape 1: the window has a fixed size
Maintain a running total instead of recomputing. Maximum sum of any k consecutive elements:
def max_sum_k(nums, k):
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best1 add, 1 subtract per step. Linear instead of n times k.
Same shape: average of subarrays of size k, permutation in a string.
Shape 2: the window grows and shrinks
The size is what you are solving for. Grow the right edge always. Shrink the left only while the window is invalid.
Longest substring without repeating characters, in Python:
def longest_unique(s):
last = {}
left = best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
best = max(best, right - left + 1)
return bestThe code is the rate limiter with a different expiry rule. Instead of dropping by age, you drop by duplicate.
Same shape: minimum window substring, smallest subarray with sum at least n.
The tell: longest or shortest window satisfying a condition. The condition gets worse as the window grows.
What makes the sliding window algorithm legal?
The condition has to be monotonic in window size. Growing can only break it, shrinking can only fix it.
Sums of positive numbers qualify. Sums with negatives do not; they need prefix sums and a hash map.
Say this in the interview:
“Sliding window needs the condition to be monotonic in the window size. All values here are positive, so growing the window only increases the sum, which means once it is too large I can safely shrink from the left.”
What are the 3 bookkeeping mistakes?
Recomputing instead of updating.
A sum or max call inside the loop rebuilds the quadratic version. Every entry and exit must be O(1).
Shrinking with if instead of while.
One new element can invalidate several positions. if handles the first and leaves the window broken.
Recording at the wrong moment.
Longest-window problems record after shrinking. Shortest-window problems record inside the shrink loop.
How do you recognise a sliding window algorithm problem in 20 seconds?
Is the answer a contiguous run? Subsequence questions are usually dynamic programming.
Is the size fixed or unknown? That picks the shape.
Does adding an element only ever hurt? That decides whether you may shrink from the left.
Three answers give you the code.
How should you practise?
Write the rate limiter from scratch, then the longest-substring problem. Notice it is the same 3 moves.
A pattern you have used you can rebuild under pressure. A pattern you have only read, not.
I built AlgoPath on this idea. Binary search as git bisect, the sliding window as a rate limiter.
The pair-problem relative is in two-pointer problems.
Common questions
When should you use a sliding window instead of two pointers?
The 2 patterns overlap, and the distinction is what you are tracking. Two pointers tracks a pair or a boundary in a sorted array. A sliding window tracks an aggregate over a contiguous run. A sum, a count, a set of distinct characters. Interviewers switch between them mid-question, so name which one you are using.
Where do you record the answer, before or after shrinking?
For longest-window problems, after shrinking. The window is only valid once the shrink loop ends. For shortest-window problems, inside the shrink loop, because every valid smaller window is a candidate. Getting this backwards produces code that looks correct and returns a number off by 1.
What if k is larger than the array?
Handle it before you are asked, because the follow-up always arrives. Return whatever the question defines as the empty answer, usually zero or None. Say so out loud while you write the guard. Volunteering the edge case is a scorecard line. Being told about it is a different one.
Does the pattern work on streams?
Yes. A rate limiter never sees the whole input and still runs the same 3 moves. The window only needs the elements currently inside it. Fixed-size shapes need a deque, variable-size shapes need whatever structure the condition is checked against.
What is the sliding window in DSA?
A sliding window keeps a running answer over a contiguous range. It moves that range along the input. Each element enters once and leaves once. The work is linear instead of quadratic. It has 2 shapes: fixed size, and one that grows and shrinks against a condition.
The short version
Shrink while invalid, grow always, record at the right moment.
Fixed size means add 1 and drop 1. Unknown size means grow right and shrink left.
The pattern is legal only when the condition is monotonic in window size. Saying so is worth more than the code.
To have this tested under time pressure, book a mock interview. A written scorecard follows within 24 hours.