Sliding-Window Rate Limiter

Start from brute force

The obvious approach keeps every accepted timestamp in a plain list and, for each new request at t, counts the entries greater than t - window; accept and append if that count is below limit. It is correct, because it measures the half-open window directly. But it rescans the whole history on every request and never forgets anything, so it costs O(n²) time in the worst case (every request accepted, each scanning all earlier ones) and O(n) space. A million requests under a high limit means on the order of 5 × 10¹¹ comparisons, all to re-check timestamps that left the window long ago.

The approach

The insight is that the window only ever slides forward. Timestamps arrive in non-decreasing order, so once an accepted request is window units old it can never count again, and the expired requests are always the oldest ones. That makes a FIFO queue exact: evict from the front, append at the back, and what remains is precisely the accepted requests in (t - window, t].

The reference keeps log, a deque of accepted timestamps, oldest first. For each t, the loop while log and log[0] <= t - window pops everything that has slid out; the <= is what makes the window half-open, so a request exactly window old is gone. Then len(log) < limit decides: accept, append t and record True; otherwise record False and leave log untouched, because rejected requests do not occupy the window. The TypeScript version gets the same effect by advancing a head index instead of popping.

Walk through an example

The first example, limit = 2, window = 10, timestamps = [1, 2, 3, 11, 12], one row per request.

Complexity

Deque log: O(1) amortized per request, because each accepted timestamp is appended once and popped at most once, so n requests cost O(n); space O(limit), since an entry is logged only while fewer than limit are present. Brute-force scan: O(n²) time in the worst case, because every request rescans the full history, and O(n) space, since nothing is evicted.

Edge cases to test

• A burst at one instant, limit = 2, window = 10, [5, 5, 5]: [True, True, False]. Equal timestamps all sit inside the same window.
• The exact boundary, limit = 1, window = 5, [0, 5]: [True, True]. At t = 5 the entry 0 is exactly window old and is evicted (0 ≤ 0).
• Rejects do not count, limit = 1, window = 5, [1, 2, 3, 4, 6]: [True, False, False, False, True]. If the rejected requests were logged, t = 6 would be rejected too.
• limit = 0, [1, 2]: [False, False]. Nothing is ever allowed.
• A long gap, limit = 2, window = 10, [1, 2, 100]: [True, True, True]. One eviction loop drains every expired entry at once.

Common mistakes

• Falling back to a fixed window, whose boundary lets a client send up to 2× the limit across the edge — the very thing sliding windows fix. With limit = 2 and 10-unit buckets, requests at 8, 9, 10 and 11 are all accepted, four inside the span (1, 11].
• Unbounded timestamp growth in the log variant (evict old entries).
• Logging rejected requests as well: rejections then keep the window full, and rate_limiter(2, 10, [1, 2, 3, 11, 12]) rejects t = 11 and t = 12 because t = 3 is still in the log.
• Evicting with < instead of <=: an entry exactly window old stays, and rate_limiter(1, 5, [0, 5]) returns [True, False].
• Accepting while len(log) <= limit: an off-by-one that lets limit + 1 requests into every window.

Follow-ups an interviewer asks next

One client sends millions of requests per window. Can you avoid storing timestamps?

Use a sliding-window counter: keep only the counts for the current and the previous fixed bucket, and estimate the rolling count as the current count plus the previous count times the fraction of the previous bucket still inside the rolling window. That is O(1) memory per client instead of O(limit), at the price of assuming the previous bucket’s requests were spread evenly, so the estimate can be off near a burst.

Enforce the limit per user across many API servers.

Keep each user’s log in a shared store, such as a Redis sorted set per user: remove members scored at or below t − window (ZREMRANGEBYSCORE), count the rest (ZCARD), and ZADD the request only if under the limit, all in one Lua script so two servers cannot both pass the check. Members must be unique, so add a request id scored by its timestamp, and expire idle keys.

Rejected requests should count, to punish clients that retry in a tight loop.

Log every request instead of only the accepted ones. A client that keeps retrying while blocked then keeps its own window full and stays blocked until it pauses for a full window. That is a policy choice, not a fix: the version here, where rejects are free, lets a client recover as soon as its oldest accepted request ages out.

Where this shows up

Sliding-window rate limiting is what you reach for when a fixed window’s edge burst is unacceptable — it makes “100 per minute” actually mean 100 in any 60-second span. It is standard in API gateways and abuse prevention where the limit has to hold across boundaries, not just within neat clock minutes.

Reference solution

from collections import deque

def rate_limiter(limit, window, timestamps):
    log = deque()      # timestamps of ACCEPTED requests, oldest at the front
    out = []
    for t in timestamps:
        while log and log[0] <= t - window:   # slide the window forward
            log.popleft()
        if len(log) < limit:
            log.append(t)                     # accept: it now occupies the window
            out.append(True)
        else:
            out.append(False)                 # rejected requests do not count
    return out


print(rate_limiter(2, 10, [1, 2, 3, 11, 12]))  # -> [True, True, False, True, True]

function rateLimiter(limit: number, window: number, timestamps: number[]): boolean[] {
  const log: number[] = [];   // accepted timestamps, oldest first
  let head = 0;               // index of the front (amortized O(1) dequeue)
  const out: boolean[] = [];
  for (const t of timestamps) {
    while (head < log.length && log[head] <= t - window) head++;  // slide window
    if (log.length - head < limit) {
      log.push(t);            // accept: now occupies the window
      out.push(true);
    } else {
      out.push(false);        // rejected: does not count
    }
  }
  return out;
}

console.log(rateLimiter(2, 10, [1, 2, 3, 11, 12])); // -> [true,true,false,true,true]