Skip to main content
Talentd

Maximum Requests Without Violating the Limit - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableGreedySliding Window13 min read
Practice this problem

Problem Statement

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:ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹ā€‹

  • 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 <= 105
  • requests[i] = [useri, timei]
  • 1 <= k <= requests.length
  • 1 <= useri, timei, window <= 105

Approach Overview

Problem 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.

Solution

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window ExpansionO(nĀ²)O(1)Useful for understanding the constraint and validating small inputs
Sorting + Two PointersO(n log n)O(1)When order does not matter and sorting simplifies min/max checks
Sliding Window + Monotonic DequesO(n)O(n)Best general solution for contiguous arrays with dynamic min/max constraints

Frequently Asked Questions

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).

Ready to solve this problem?

Practice Maximum Requests Without Violating the Limit with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays