Rate Limiter — Count Dropped Requests

Problem Statement

You are building a rate limiter for an API gateway. Given a sorted list of request timestamps (in seconds), implement a function to return the number of dropped requests based on these constraints:

1. A maximum of N requests are allowed in any rolling window of T seconds
2. If a request arrives and the window already has N requests, it is dropped

Your function should process all timestamps in order and return the total count of dropped requests.

Constraints

• 1 <= timestamps.length <= 10^6
• Timestamps are sorted in non-decreasing order
• 1 <= N <= 1000 (max requests per window)
• 1 <= T <= 3600 (window size in seconds)
• Timestamps are positive integers

Example

Input:

timestamps = [1, 1, 1, 1, 2, 2, 3, 5, 5, 6]
N = 3  (max 3 requests per window)
T = 2  (rolling window of 2 seconds)

Output: 4 (4 requests were dropped)

Explanation:

• t=1: requests 1,2,3 accepted. Request 4 dropped (3 already in window [0,2])
• t=2: window [1,3] already has 3 from t=1 → requests at t=2 dropped
• t=3: window [2,4] — some expire, new ones accepted
• t=5,6: window moved forward, accepted

Follow-ups

1. What if timestamps arrive out of order? How would you modify the approach?
2. How would you implement this for a distributed system with multiple servers?
3. What data structure would you use if you needed O(1) amortized per request?
4. How does this compare to token bucket vs leaky bucket approaches?