Problem

NovaAPI wants to limit how many requests each user can make within a fixed time window. Implement a rate limiter that decides whether an incoming request should be allowed based on that user's recent request timestamps.

Task

Write a function that processes a list of requests and returns whether each request is allowed.

Each request is represented as [user_id, timestamp]. For a given user, a request is allowed if that user has made fewer than limit allowed requests in the inclusive interval [timestamp - window_size + 1, timestamp]. Otherwise, the request is rejected.

Timestamps are given in non-decreasing order across the full input.

Input / Output

• Input: requests as a list of [user_id, timestamp], limit as an integer, and window_size as an integer.
• Output: A list of booleans where each element indicates whether the corresponding request is allowed.

Examples

Example 1

• Input: requests = [[1, 1], [1, 2], [1, 3], [1, 4]], limit = 2, window_size = 3
• Output: [true, true, false, true]
• Explanation: At timestamp 3, user 1 already has allowed requests at 1 and 2 within window [1, 3], so the third request is rejected. At timestamp 4, the window is [2, 4], so timestamp 1 expires.

Example 2

• Input: requests = [[1, 1], [2, 1], [1, 2], [2, 2], [1, 3]], limit = 2, window_size = 2
• Output: [true, true, true, true, true]
• Explanation: Each user is tracked independently.

Constraints

• 1 <= len(requests) <= 10^5
• 1 <= user_id <= 10^9
• 1 <= timestamp <= 10^9
• 1 <= limit <= 10^5
• 1 <= window_size <= 10^9
• Request timestamps are in non-decreasing order.