You are given a 2D integer array requests, where requests[i] = [useri, timei] indicates that useri made a request at timei.
You are also given two integers k and window.
A user violates the limit if there exists an integer t such that the user makes strictly more than k requests in the inclusive interval [t, t + window].
You may drop any number of requests.
Return an integer denoting the maximum number of requests that can remain such that no user violates the limit.
Example 1:
Input: requests = [[1,1],[2,1],[1,7],[2,8]], k = 1, window = 4
Output: 4
Explanation:
[1, 7]. The difference between them is 6, which is greater than window = 4.[1, 8]. The difference is 7, which is also greater than window = 4.k = 1 request within any inclusive interval of length window. Therefore, all 4 requests can remain.Example 2:
Input: requests = [[1,2],[1,5],[1,2],[1,6]], k = 2, window = 5
Output: 2
Explanation:
[2, 2, 5, 6]. The inclusive interval [2, 7] of length window = 5 contains all 4 requests.k = 2, at least 2 requests must be removed.window contains at most k = 2 requests.Example 3:
Input: requests = [[1,1],[2,5],[1,2],[3,9]], k = 1, window = 1
Output: 3
Explanation:
[1, 2]. The difference is 1, which is equal to window = 1.[1, 2] contains both requests, so the count is 2, which exceeds k = 1. One request must be removed.
Constraints:
1 <= requests.length <= 105requests[i] = [useri, timei]1 <= k <= requests.length1 <= useri, timei, window <= 105We can group the requests by user and store them in a hash table g, where g[u] is the list of request times for user u. For each user, we need to remove some requests from the request time list so that within any interval of length window, the number of remaining requests does not exceed k.
We initialize the answer ans to the total number of requests.
For the request time list g[u] of user u, we first sort it. Then, we use a deque kept to maintain the currently kept request times. We iterate through each request time t in the request time list. For each request time, we need to remove all request times from kept whose difference from t is greater than window. Then, if the number of remaining requests in kept is less than k, we add t to kept; otherwise, we need to remove t and decrement the answer by 1.
Finally, return the answer ans.
The time complexity is O(n log n) and the space complexity is O(n), where n is the number of requests. Each request is visited once, sorting takes O(n log n) time, and the operations on the hash table and deque take O(n) time.
Java
C++
Go
TypeScript
Rust
Practice Maximum Requests Without Violating the Limit with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor