All problems

Rate Limiter Log

Medium · queue

A service limits how often each user may call it. You are given a log of requests: request k was made by user users[k] at second times[k]. The times never decrease from one request to the next.

A request at second t is accepted if fewer than limit of that same user's accepted requests have a time in the range (t - window, t]. That range includes t itself but not t - window: a request made exactly window seconds after an accepted one no longer sees it. Otherwise the request is rejected. Rejected requests are never counted against anyone, and different users do not affect each other.

Process the requests in the given order and return a list with one boolean per request: true if it is accepted and false if it is rejected.

Examples

Example 1

Input: times = [1, 2, 3, 4, 6], users = [7, 7, 7, 7, 7], limit = 2, window = 3

Output: [true, true, false, true, true]

At second 3 the range (0, 3] already holds two accepted requests, so it is rejected. At second 4 the range (1, 4] holds only the one from second 2.

Example 2

Input: times = [0, 1, 3, 3], users = [5, 5, 5, 5], limit = 1, window = 3

Output: [true, false, true, false]

The request at second 3 is exactly 3 seconds after the accepted one at second 0, so that one has expired and the request is accepted. The second request at second 3 is then rejected.

Example 3

Input: times = [1, 1, 2, 2, 3], users = [1, 2, 1, 1, 2], limit = 2, window = 2

Output: [true, true, true, false, true]

User 1 has two accepted requests by second 2, so a third is rejected. User 2 is counted separately.

Constraints