3851. Maximum Requests Without Violating the Limit 🔒

MediumGreedyArrayHash TableSortingSliding Window

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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

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]. In other words, looking at any time span whose length equals window, a single user is not allowed to have more than k requests falling inside that span.

You may drop any number of requests. Dropping a request simply means removing it from the list so it no longer counts toward any user's limit.

Your task is to return an integer denoting the maximum number of requests that can remain such that no user violates the limit.

For example, if a user has many requests clustered closely together, you must drop just enough of them so that within every window of length window, that user keeps at most k requests. The goal across all users is to keep as many requests as possible in total.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Greedy Algorithms?

This problem maps to Greedy Algorithms through a short path in the full flowchart.

Greedy per-user sliding window maximizes kept requests by keeping earliest valid ones.

Open in Flowchart

Intuition

The first observation is that each user's limit is completely independent of every other user. One user's requests have no effect on whether another user violates the limit. This means we can handle each user separately: process the requests of one user at a time, figure out the maximum number of requests we can keep for that user, and then add up the results across all users. So our first step is to group the requests by user.

Now the problem reduces to a single-user question: given a list of request times, we must keep as many as possible while ensuring that within any window of length window, at most k requests remain. To make the time relationships easy to reason about, we sort each user's request times. After sorting, requests that are close in time are also close in the list, so we can scan from earliest to latest and only ever look at a contiguous group of recent requests.

The key insight is a greedy one. As we walk through the sorted times, we want to keep a request whenever doing so does not break the rule. A request at time t only conflicts with other kept requests whose times lie within window of it. So we maintain a sliding window (a deque) of the requests we have decided to keep that are still "active," meaning their time is within window of the current request t. Any kept request older than t - window can never conflict with t or anything after it, so we safely remove it from the front.

For the current request t, we look at how many requests are still active in the deque:

If there are fewer than k active requests, keeping t is safe, so we add it to the deque.
If there are already k active requests, keeping t would create more than k requests inside a window, so we must drop t and decrease our answer count by 1.

Why is this greedy choice optimal? Because we process times in increasing order, keeping an earlier request is never worse than keeping a later one — an earlier request leaves the window of conflict sooner, freeing up room for future requests. So whenever we can keep a request without violating the limit, keeping it can only help.

We start the answer as the total number of requests and subtract one each time we are forced to drop a request, giving us the maximum number that can remain.

Pattern Learn more about Greedy, Sorting and Sliding Window patterns.

Solution Approach

Solution 1: Sliding Window + Deque

We 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. We build this by iterating over requests and appending each time t to the list of its corresponding user u.

We initialize the answer ans to the total number of requests, len(requests). We start by assuming every request can be kept, then subtract one for each request we are forced to drop.

Next, we process each user's request time list g[u] independently. For each list ts:

We first sort ts so the times are in increasing order. This lets us scan from earliest to latest and only compare against recent requests.
We use a deque kept to maintain the times of the requests we have decided to keep that are still active, meaning their time is within window of the current request.
We iterate through each request time t in ts:
- First, we remove from the front of kept every time whose difference from t exceeds window, i.e. while kept is non-empty and t - kept[0] > window, we call kept.popleft(). These removed requests can no longer conflict with t or any later request.
- Then we check the size of kept:
  - If len(kept) < k, keeping t is safe, so we append t to kept.
  - Otherwise, keeping t would push the count above k inside a window, so we drop t and decrement ans by 1.

After processing all users, we return ans.

Why a deque? The deque acts as a sliding window over the kept requests. We always add new times at the back and remove expired times from the front, both in O(1) time. Its length directly tells us how many kept requests currently lie within window of the current request, which is exactly the value we compare against k.

Complexity Analysis:

Time complexity: O(n × log n), where n is the number of requests. The dominant cost is sorting each user's request times; the sum of all users' list lengths is n, so the total sorting cost is bounded by O(n × log n). The deque scan visits each request a constant number of times.
Space complexity: O(n), for the hash table g grouping all requests and the deque kept.

Example Walkthrough

Let's trace through a small example to see the greedy sliding-window approach in action.

Input:

requests = [[1, 2], [1, 5], [1, 6], [1, 9], [2, 4]]
k = 2
window = 3

This means user 1 made requests at times 2, 5, 6, 9, and user 2 made one request at time 4. The rule is: within any window of length 3, a single user may keep at most 2 requests.

Step 1: Group requests by user.

We build the hash table g:

g[1] = [2, 5, 6, 9]
g[2] = [4]

We initialize ans = len(requests) = 5, assuming every request can be kept.

Step 2: Process user 1 — ts = [2, 5, 6, 9].

After sorting, the list is already [2, 5, 6, 9]. We use an empty deque kept and scan each time t:

`t`	Remove expired (`t - kept[0] > 3`)	`kept` before check	`len(kept) < k`?	Action	`kept` after	`ans`
2	nothing to remove	`[]`	`0 < 2` ✓	keep → append	`[2]`	5
5	`5 - 2 = 3`, not `> 3`, keep	`[2]`	`1 < 2` ✓	keep → append	`[2, 5]`	5
6	`6 - 2 = 4 > 3`, pop `2`	`[5]`	`1 < 2` ✓	keep → append	`[5, 6]`	5
9	`9 - 5 = 4 > 3`, pop `5`; `9 - 6 = 3`, stop	`[6]`	`1 < 2` ✓	keep → append	`[6, 9]`	5

For user 1, no request is ever dropped. Let's verify: the only window where two requests cluster is [5, 6] (within length 3), which has exactly 2 requests — that's allowed. So all four requests survive.

Step 3: Process user 2 — ts = [4].

A single time 4. The deque starts empty, len(kept) = 0 < 2, so we keep it. ans stays 5.

Step 4: Return the answer.

No request was forced to be dropped, so ans = 5.

A contrasting case (why dropping happens):

Suppose user 1 instead had times [2, 3, 4] with k = 2, window = 3:

`t`	Remove expired	`kept` before	`len(kept) < k`?	Action	`kept` after	`ans`
2	none	`[]`	`0 < 2` ✓	keep	`[2]`	3
3	`3 - 2 = 1`, keep	`[2]`	`1 < 2` ✓	keep	`[2, 3]`	3
4	`4 - 2 = 2`, keep	`[2, 3]`	`2 < 2` ✗	drop → `ans -= 1`	`[2, 3]`	2

Here the window [2, 4] would hold three requests, exceeding k = 2, so we are forced to drop the request at time 4, leaving ans = 2. This shows how the deque's length directly signals when the limit would be violated, triggering a drop.

Solution Implementation

1from collections import defaultdict, deque
2
3
4class Solution:
5    def maxRequests(self, requests: list[list[int]], k: int, window: int) -> int:
6        # Group all request timestamps by user id.
7        # user_timestamps[user] = list of timestamps for that user.
8        user_timestamps: dict[int, list[int]] = defaultdict(list)
9        for user, timestamp in requests:
10            user_timestamps[user].append(timestamp)
11
12        # Start by assuming every request can be kept,
13        # then subtract the ones we are forced to drop.
14        max_kept = len(requests)
15
16        # Process each user independently since the constraint
17        # (at most k requests within any window) is per-user.
18        for timestamps in user_timestamps.values():
19            # Sort timestamps so we can use a sliding window.
20            timestamps.sort()
21
22            # kept_window holds the timestamps currently inside
23            # the active time window for this user.
24            kept_window: deque[int] = deque()
25
26            for current_time in timestamps:
27                # Slide the window forward: discard timestamps that are
28                # now older than `window` relative to current_time.
29                while kept_window and current_time - kept_window[0] > window:
30                    kept_window.popleft()
31
32                if len(kept_window) < k:
33                    # There is still room in this window, so keep the request.
34                    kept_window.append(current_time)
35                else:
36                    # The window is already full (k requests),
37                    # so this request must be dropped.
38                    max_kept -= 1
39
40        return max_kept
41

1class Solution {
2    public int maxRequests(int[][] requests, int k, int window) {
3        // Group request timestamps by user id.
4        // key   -> user id
5        // value -> list of timestamps for that user
6        Map<Integer, List<Integer>> userTimestamps = new HashMap<>();
7        for (int[] request : requests) {
8            int userId = request[0];
9            int timestamp = request[1];
10            userTimestamps
11                .computeIfAbsent(userId, key -> new ArrayList<>())
12                .add(timestamp);
13        }
14
15        // Start by assuming all requests can be accepted,
16        // then subtract the ones we are forced to reject.
17        int acceptedCount = requests.length;
18
19        // Sliding window of kept (accepted) timestamps for the current user.
20        // The deque always holds timestamps within the allowed window range.
21        ArrayDeque<Integer> keptTimestamps = new ArrayDeque<>();
22
23        // Process each user independently.
24        for (List<Integer> timestamps : userTimestamps.values()) {
25            // Sort timestamps so we can apply the sliding window in order.
26            Collections.sort(timestamps);
27
28            // Reset the window for the new user.
29            keptTimestamps.clear();
30
31            for (int currentTimestamp : timestamps) {
32                // Evict timestamps that fall outside the window
33                // (older than currentTimestamp - window).
34                while (!keptTimestamps.isEmpty()
35                        && currentTimestamp - keptTimestamps.peekFirst() > window) {
36                    keptTimestamps.pollFirst();
37                }
38
39                // If the window still has capacity (fewer than k accepted),
40                // accept this request and keep its timestamp.
41                if (keptTimestamps.size() < k) {
42                    keptTimestamps.addLast(currentTimestamp);
43                } else {
44                    // Otherwise the window is full within the limit,
45                    // so this request must be rejected.
46                    --acceptedCount;
47                }
48            }
49        }
50
51        return acceptedCount;
52    }
53}
54

1class Solution {
2public:
3    int maxRequests(vector<vector<int>>& requests, int k, int window) {
4        // Group request timestamps by their key (e.g., user/source id).
5        // groupedTimestamps[id] holds all timestamps belonging to that id.
6        unordered_map<int, vector<int>> groupedTimestamps;
7        for (auto& request : requests) {
8            int id = request[0];
9            int timestamp = request[1];
10            groupedTimestamps[id].push_back(timestamp);
11        }
12
13        // Start by assuming every request can be kept, then subtract the ones
14        // that must be dropped because they violate the window/limit rule.
15        int remainingRequests = static_cast<int>(requests.size());
16
17        // Process each id independently since limits apply per id.
18        for (auto& [id, timestamps] : groupedTimestamps) {
19            // Sort timestamps so we can use a sliding window from left to right.
20            sort(timestamps.begin(), timestamps.end());
21
22            // keptWindow stores the timestamps currently kept within the window.
23            // The front is the oldest kept timestamp.
24            queue<int> keptWindow;
25
26            for (int currentTime : timestamps) {
27                // Evict timestamps that fall outside the allowed window
28                // relative to the current timestamp.
29                while (!keptWindow.empty() &&
30                       currentTime - keptWindow.front() > window) {
31                    keptWindow.pop();
32                }
33
34                if (static_cast<int>(keptWindow.size()) < k) {
35                    // There is room within the window; keep this request.
36                    keptWindow.push(currentTime);
37                } else {
38                    // The window is already full; this request must be dropped.
39                    remainingRequests--;
40                }
41            }
42        }
43
44        return remainingRequests;
45    }
46};
47

1/**
2 * Determines the maximum number of requests that can be kept, given the
3 * constraint that for each user no more than `k` requests may fall inside
4 * any sliding time window of length `window`.
5 *
6 * @param requests - A list of [userId, timestamp] pairs.
7 * @param k        - The maximum number of requests allowed per user within any window.
8 * @param window   - The length of the sliding time window.
9 * @returns The maximum number of requests that can be retained.
10 */
11function maxRequests(requests: number[][], k: number, window: number): number {
12    // Group every request timestamp by its user id.
13    const userToTimestamps = new Map<number, number[]>();
14    for (const [userId, timestamp] of requests) {
15        if (!userToTimestamps.has(userId)) {
16            userToTimestamps.set(userId, []);
17        }
18        userToTimestamps.get(userId)!.push(timestamp);
19    }
20
21    // Start by assuming every request can be kept, then subtract the ones we drop.
22    let answer = requests.length;
23
24    // Process each user independently.
25    for (const timestamps of userToTimestamps.values()) {
26        // Sort this user's timestamps in ascending order so we can use a sliding window.
27        timestamps.sort((a, b) => a - b);
28
29        // `kept` stores the timestamps we decide to retain for this user.
30        const kept: number[] = [];
31        // `head` is the left boundary of the sliding window inside `kept`.
32        let head = 0;
33
34        for (const timestamp of timestamps) {
35            // Advance the window's left boundary past any timestamps that are
36            // now outside the current window.
37            while (head < kept.length && timestamp - kept[head] > window) {
38                head++;
39            }
40
41            // If fewer than `k` kept requests lie within the current window,
42            // we can keep this request as well.
43            if (kept.length - head < k) {
44                kept.push(timestamp);
45            } else {
46                // Otherwise we must drop this request, reducing the total count.
47                --answer;
48            }
49        }
50    }
51
52    return answer;
53}
54

Time and Space Complexity

Time Complexity: O(n log n), where n is the total number of requests.

Building the hash table g requires iterating over all requests once, costing O(n).
For each user, the request timestamps are sorted. Although sorting happens per user, the total number of timestamps across all users equals n. By the property that Σ mᵢ log mᵢ ≤ (Σ mᵢ) log(Σ mᵢ) = n log n (where mᵢ is the number of requests for user i), the combined sorting cost is bounded by O(n log n).
The sliding-window pass using the deque processes each timestamp a constant number of times: each timestamp is appended at most once and popped at most once via popleft. Across all users this amounts to O(n).
Overall, the dominant term is the sorting step, giving O(n log n).

Space Complexity: O(n), where n is the total number of requests.

The hash table g stores every request's timestamp grouped by user, using O(n) space in total.
The deque kept holds at most the timestamps within a single user's window, which is bounded by that user's request count, and overall never exceeds O(n).
Therefore, the total auxiliary space is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Dropping the Wrong Request (Greedy Direction Error)

A frequent mistake is, when the window is "full," dropping an earlier kept request instead of the current one. Some implementations instinctively try to "make room" by evicting kept_window[0] and then appending current_time:

# WRONG: evicting an already-kept request to keep the current one
if len(kept_window) >= k:
    kept_window.popleft()   # drop an earlier request
    max_kept -= 1
kept_window.append(current_time)

Why it's wrong: Once we have already committed to keeping the first k requests in a window, those earlier requests are "safer" to keep than later ones. A request kept earlier conflicts only with requests that come after it, while a request kept later can conflict with everything in its trailing window. Greedily keeping the earliest valid requests and dropping the current one whenever the window is full is the choice that maximizes the total kept. Swapping which request we drop produces the same count in this isolated step but can corrupt the window state, leading to incorrect counts down the line.

Solution: When len(kept_window) == k, simply drop the current request (do not append it, just decrement max_kept). Never evict from kept_window to make room.

Pitfall 2: Misinterpreting the Window as Half-Open or Off-by-One

The interval [t, t + window] is inclusive on both ends, so its span allows differences up to and including window. A common error is using the wrong comparison operator when sliding the window:

# WRONG: removes timestamps that are still inside the inclusive window
while kept_window and current_time - kept_window[0] >= window:
    kept_window.popleft()

Using >= window incorrectly evicts a timestamp whose difference is exactly window, even though t and t + window lie in the same inclusive interval and should count together.

Solution: Use strict greater-than:

while kept_window and current_time - kept_window[0] > window:
    kept_window.popleft()

This keeps any pair of timestamps whose difference is ≤ window in the same active window, matching the inclusive [t, t + window] definition.

Pitfall 3: Forgetting to Sort Each User's Timestamps

The sliding-window logic relies on processing timestamps in increasing order. If the input order is preserved (requests can arrive out of chronological order in the array), the current_time - kept_window[0] comparison becomes meaningless—kept_window[0] may not be the oldest active timestamp, and you could even compute negative differences.

# WRONG: skipping the sort
for timestamps in user_timestamps.values():
    kept_window = deque()
    for current_time in timestamps:   # timestamps may be unordered!
        ...

Solution: Always timestamps.sort() before scanning. Sorting guarantees kept_window stays monotonically increasing, so the front is always the oldest entry and the popleft() eviction is valid.

Pitfall 4: Applying the Constraint Globally Instead of Per-User

The limit is per user, not across all requests combined. Merging all timestamps into a single window and counting violations globally over-drops requests and yields a number that is too small.

Solution: Group by user first (as done with user_timestamps), then run an independent sliding window per user. Each user gets a fresh kept_window, and the global max_kept accumulates the drops from every user separately.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering