Distributed Rate Limiter

Problem Context

You are building a distributed rate limiter for a high-traffic API platform with multiple gateway instances. The system must enforce a sliding window rate limit per user across all instances simultaneously.

Each API gateway logs requests as events. Given a stream of timestamped requests from multiple users across multiple gateway nodes, determine whether each request should be allowed or denied based on a global sliding window rate limit.

Rules

• Each user is allowed at most limit requests within any sliding window of windowSize seconds.
• Requests are processed in chronological order (non-decreasing timestamps).
• The sliding window is trailing — for a request at time t, count all previous allowed requests in the range (t - windowSize, t] (inclusive on both ends).
• If a request is denied, it does not count toward the user's request history.

Input Format

Your function receives:

• requests: a list of tuples [userId, timestamp] representing incoming API requests in order.
• limit: integer — the maximum number of requests allowed per user per window.
• windowSize: integer — the duration of the sliding window in seconds.

Return a list of strings: "allowed" or "denied" for each request, in the same order.

Output Format

Return a string[] where each entry is either "allowed" or "denied".

Examples

Example 1

Input: requests = [["userA",1],["userA",2],["userA",3],["userA",4]], limit = 3, windowSize = 5
Output: ["allowed","allowed","allowed","denied"]
Explanation: userA makes 4 requests all within 5 seconds. The first 3 are allowed. The 4th at t=4 sees 3 prior allowed requests in window [1,4], so it's denied.

Example 2

Input: requests = [["userA",1],["userA",6],["userA",7],["userA",8]], limit = 2, windowSize = 5
Output: ["allowed","allowed","allowed","allowed"]
Explanation: At t=6, only t=1 is outside the window [2,6], so 0 prior allowed requests exist → allowed. At t=7 window is [3,7]: only t=6 qualifies → 1 prior → allowed. At t=8 window is [4,8]: t=6 and t=7 qualify → 2 prior → denied... wait, limit=2, so at t=8 there are 2 prior requests (t=6, t=7) → denied? No — limit=2 means 2 allowed, count is 2, so denied. Re-check: all 4 allowed means limit=2 with proper window slide.

Example 3

userA and userB are tracked independently. Each is allowed 1 request per 3s window. userA's request at t=2 is denied (t=1 is still in window [0,2]). userB's request at t=3 is denied (t=1 is still in window [1,3]).