Is Maximum Requests Without Violating the Limit easy or hard?

The problem is typically classified as Medium. The challenge is recognizing that naive range checks are too slow and that a monotonic deque can maintain minimum and maximum values efficiently within a sliding window.

Maximum Requests Without Violating the Limit Python/Java solution

Most implementations follow the same structure: maintain two deques storing indices, update them while expanding the window, and shrink the window when the limit is exceeded. The algorithm works identically in Python, Java, C++, Go, TypeScript, and Rust with O(n) time complexity.

How to solve Maximum Requests Without Violating the Limit in O(n)?

Maintain a sliding window with two monotonic deques: one decreasing deque for the maximum and one increasing deque for the minimum. Expand the right pointer while inserting elements into both deques. If max minus min exceeds the limit, move the left pointer and remove outdated indices. Track the largest valid window length during the scan.

What is the best approach for Maximum Requests Without Violating the Limit?

The optimal approach uses a sliding window combined with two monotonic deques to track the current maximum and minimum values. As the window expands, the deques maintain ordered indices so the range can be checked in O(1) time. Each element is inserted and removed at most once, resulting in O(n) time complexity.

Is Maximum Requests Without Violating the Limit asked at Google/Amazon/Meta?

Problems using sliding windows with monotonic queues appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as 'Longest Continuous Subarray With Absolute Difference Less Than or Equal to Limit' test the same pattern of maintaining dynamic min and max values efficiently.

What data structure is used in Maximum Requests Without Violating the Limit?

The key data structure is a monotonic deque (double-ended queue). One deque keeps elements in decreasing order to retrieve the maximum quickly, while another keeps elements in increasing order to retrieve the minimum. This allows constant-time range checks inside the sliding window.

What is the time complexity of Maximum Requests Without Violating the Limit?

The optimal sliding window + deque solution runs in O(n) time and uses O(n) space. Every element is pushed and popped from the deques at most once. A brute force solution would take O(n^2) time, while a sorting-based approach runs in O(n log n).

3851. Maximum Requests Without Violating the Limit - Practice Online

You are given a 2D integer array requests, where requests[i] = [user_i, time_i] indicates that user_i made a request at time_i.

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:

For user 1, the request times are [1, 7]. The difference between them is 6, which is greater than window = 4.
For user 2, the request times are [1, 8]. The difference is 7, which is also greater than window = 4.
No user makes more than 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:

For user 1, the request times are [2, 2, 5, 6]. The inclusive interval [2, 7] of length window = 5 contains all 4 requests.
Since 4 is strictly greater than k = 2, at least 2 requests must be removed.
After removing any 2 requests, every inclusive interval of length window contains at most k = 2 requests.
Therefore, the maximum number of requests that can remain is 2.

Example 3:

Input: requests = [[1,1],[2,5],[1,2],[3,9]], k = 1, window = 1

Output: 3

Explanation:

For user 1, the request times are [1, 2]. The difference is 1, which is equal to window = 1.
The inclusive interval [1, 2] contains both requests, so the count is 2, which exceeds k = 1. One request must be removed.
Users 2 and 3 each have only one request and do not violate the limit. Therefore, the maximum number of requests that can remain is 3.

Constraints:

1 <= requests.length <= 10⁵
requests[i] = [user_i, time_i]
1 <= k <= requests.length
1 <= user_i, time_i, window <= 10⁵