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 <= 105Problem Overview: You are given a sequence of request values and a limit. The goal is to select the largest contiguous group of requests such that the difference between the maximum and minimum value inside that window never exceeds the given limit.
Approach 1: Brute Force Window Expansion (O(n2) time, O(1) space)
Start every subarray at index i and expand it one element at a time. Track the current minimum and maximum values while extending the range. If max - min exceeds the allowed limit, stop expanding that window and move to the next starting index. This approach is straightforward and demonstrates the core constraint check, but it repeatedly recomputes ranges and becomes slow for large arrays.
Approach 2: Sorting + Two Pointers (O(n log n) time, O(1) extra space)
If request order is not required, sort the array first. After sorting, the minimum and maximum of any window are simply the first and last elements. Use two pointers to expand the right boundary while maintaining nums[right] - nums[left] <= limit. If the difference exceeds the limit, move the left pointer forward. Sorting costs O(n log n), but the scan itself is linear. This approach leverages ordering to simplify range checks and is commonly paired with sorting and greedy strategies.
Approach 3: Sliding Window + Monotonic Deques (O(n) time, O(n) space)
The optimal solution keeps a sliding window while maintaining the current maximum and minimum using two monotonic deque structures. One deque stores indices in decreasing order to track the window maximum; the other stores indices in increasing order to track the window minimum. As you expand the right pointer, remove elements from the back that break the monotonic property. If the difference between the front elements of the two deques exceeds the limit, shrink the window from the left and remove outdated indices. Each element enters and leaves a deque at most once, giving O(n) time complexity. This technique combines sliding window mechanics with efficient range tracking using a deque-based structure.
Recommended for interviews: The sliding window with monotonic deques is the expected solution. Brute force shows you understand the constraint check, but the optimized window demonstrates mastery of maintaining dynamic min/max values in constant time. Interviewers often use this pattern to test knowledge of monotonic queues and advanced sliding window optimization.
We 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Window Expansion | O(n²) | O(1) | Useful for understanding the constraint and validating small inputs |
| Sorting + Two Pointers | O(n log n) | O(1) | When order does not matter and sorting simplifies min/max checks |
| Sliding Window + Monotonic Deques | O(n) | O(n) | Best general solution for contiguous arrays with dynamic min/max constraints |
Practice Maximum Requests Without Violating the Limit with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor