LeetCode Problem 3851

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Sliding Window, Sorting

Solution

LeetCode 3851 - Maximum Requests Without Violating the Limit

Problem Understanding

We are given a list of requests, where each request consists of a user ID and a timestamp. Multiple users can appear in the input, and a user may have multiple requests at different times.

For a particular user, the rate limit rule states that in any inclusive interval [t, t + window], the number of requests made by that user must be at most k. If there exists even one interval containing more than k requests from the same user, that user violates the limit.

We are allowed to remove any number of requests. Our goal is to maximize the number of requests that remain while ensuring that no user violates the limit.

An important observation is that requests from different users are completely independent. A violation only depends on requests belonging to the same user. Therefore, we can process each user's requests separately and then sum the number of requests we keep.

The constraints are large:

• requests.length ≤ 100,000
• useri ≤ 100,000
• timei ≤ 100,000

This immediately rules out any solution that examines all intervals explicitly or repeatedly scans large portions of the data.

Some important edge cases include:

• Multiple requests occurring at exactly the same timestamp.
• window = 1, where adjacent timestamps can still belong to the same inclusive interval.
• Large groups of requests belonging to a single user.
• Cases where every request must be removed except a few.
• Cases where all requests can remain.

The inclusive interval definition is especially important. If two timestamps differ by exactly window, they still belong to the same valid interval and therefore count together.

Approaches

Brute Force

A brute-force strategy would process each user separately and try every possible subset of requests to determine the largest valid subset.

For a user with m requests, this would require checking up to 2^m subsets. For each subset, we would need to verify whether any interval of length window contains more than k requests.

This approach is obviously infeasible even for moderate values of m.

A slightly better brute-force idea is to repeatedly check every request against every other request, counting how many requests fall into each window. Even this quickly becomes quadratic, which is too slow for 100,000 requests.

Key Insight

Consider one user's request timestamps after sorting:

t1 ≤ t2 ≤ t3 ≤ ... ≤ tm

Suppose we are deciding whether to keep each request.

When we reach timestamp ti, the only requests that matter are previously kept requests whose timestamps lie within:

[ti - window, ti]

If there are already k kept requests inside this range, then keeping ti would create a window containing k + 1 requests, violating the rule.

Therefore:

• If fewer than k kept requests currently lie inside the active window, we should keep ti.
• Otherwise, we must discard ti.

This greedy choice is optimal.

Why? Keeping an earlier request is always at least as good as replacing it with a later request. Earlier requests expire from future windows sooner, making them more flexible. Therefore, whenever a conflict occurs, discarding the newest request is never worse than discarding an older kept request.

This leads naturally to a sliding window approach.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^m) per user, or worse	O(m)	Enumerates subsets or repeatedly checks intervals
Optimal	O(n log n)	O(n)	Sort timestamps per user and use greedy sliding window

Algorithm Walkthrough

Step 1

Group all request timestamps by user.

A hash map is ideal because we need to efficiently collect all timestamps belonging to the same user.

Step 2

For each user, sort that user's timestamps.

The rate limit depends only on chronological order, so sorting allows us to process requests from earliest to latest.

Step 3

Maintain a queue of timestamps that have been kept.

This queue represents the kept requests currently inside the active window.

Step 4

Process timestamps in sorted order.

Before considering the current timestamp t, remove timestamps from the front of the queue while:

old_timestamp < t - window

These requests can no longer participate in any interval ending at t.

Step 5

After cleanup, the queue contains exactly the kept requests within:

[t - window, t]

If the queue size is less than k, keep the current request:

• Add it to the queue.
• Increment the answer.

Otherwise, discard the request.

Step 6

Repeat for every timestamp of every user.

The total number of kept requests is the final answer.

Why it works

At every timestamp, the queue contains all previously kept requests that would share an inclusive window with the current request.

If fewer than k such requests exist, keeping the current request cannot violate the limit. If exactly k already exist, adding the current request would immediately create a window containing k + 1 requests, which is forbidden.

The greedy decision to keep a request whenever possible is optimal because earlier kept requests expire sooner and therefore restrict future choices less than later requests. Consequently, rejecting the current request whenever a conflict occurs always preserves the maximum possible number of requests.

Python Solution

from collections import defaultdict, deque
from typing import List

class Solution:
    def maxRequests(self, requests: List[List[int]], k: int, window: int) -> int:
        user_times = defaultdict(list)

        for user, time in requests:
            user_times[user].append(time)

        kept_requests = 0

        for times in user_times.values():
            times.sort()

            active = deque()

            for t in times:
                while active and active[0] < t - window:
                    active.popleft()

                if len(active) < k:
                    active.append(t)
                    kept_requests += 1

        return kept_requests

The implementation begins by grouping timestamps by user using a hash map.

For each user, the timestamps are sorted so that requests are processed chronologically.

The active deque stores kept requests that are still inside the current sliding window. Before handling a new timestamp, expired timestamps are removed from the front.

After cleanup, the deque size equals the number of already kept requests within distance window of the current timestamp. If fewer than k requests are present, the current request can safely remain and is added to the deque. Otherwise, it must be discarded.

The total count of kept requests is accumulated and returned.

Go Solution

package main

import (
	"sort"
)

func maxRequests(requests [][]int, k int, window int) int {
	userTimes := make(map[int][]int)

	for _, req := range requests {
		user := req[0]
		time := req[1]
		userTimes[user] = append(userTimes[user], time)
	}

	kept := 0

	for _, times := range userTimes {
		sort.Ints(times)

		active := make([]int, 0)
		head := 0

		for _, t := range times {
			for head < len(active) && active[head] < t-window {
				head++
			}

			if len(active)-head < k {
				active = append(active, t)
				kept++
			}
		}
	}

	return kept
}

The Go version uses a map from user ID to timestamp slices.

Instead of a deque, it uses a slice plus a head pointer. This avoids repeatedly removing elements from the front of a slice, which would be inefficient. The number of active requests is simply len(active) - head.

All values fit comfortably within Go's standard int type under the given constraints.

Worked Examples

Example 1

requests = [[1,1],[2,1],[1,7],[2,8]]
k = 1
window = 4

User 1 timestamps:

[1, 7]

Timestamp	Active Before	Keep?	Active After
1	[]	Yes	[1]
7	[]	Yes	[7]

Kept: 2

User 2 timestamps:

[1, 8]

Timestamp	Active Before	Keep?	Active After
1	[]	Yes	[1]
8	[]	Yes	[8]

Kept: 2

Total:

2 + 2 = 4

Answer:

4

Example 2

requests = [[1,2],[1,5],[1,2],[1,6]]
k = 2
window = 5

Sorted timestamps:

[2, 2, 5, 6]

Timestamp	Active Before	Size	Keep?	Active After
2	[]	0	Yes	[2]
2	[2]	1	Yes	[2,2]
5	[2,2]	2	No	[2,2]
6	[2,2]	2	No	[2,2]

Total kept:

2

Answer:

2

Example 3

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

User 1 timestamps:

[1, 2]

Timestamp	Active Before	Keep?	Active After
1	[]	Yes	[1]
2	[1]	No	[1]

Kept for user 1:

1

Users 2 and 3 each contribute one request.

Total:

1 + 1 + 1 = 3

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the running time
Space	O(n)	Stores grouped timestamps and sliding windows

Let n be the total number of requests.

Grouping requests requires O(n) time. If user groups have sizes m1, m2, ..., mr, sorting costs:

m1 log m1 + m2 log m2 + ... + mr log mr

This is bounded by O(n log n).

The sliding window processing is linear because each timestamp enters and leaves the queue at most once.

The hash map and per-user storage together require O(n) space.

Test Cases

sol = Solution()

assert sol.maxRequests([[1,1],[2,1],[1,7],[2,8]], 1, 4) == 4  # Example 1
assert sol.maxRequests([[1,2],[1,5],[1,2],[1,6]], 2, 5) == 2  # Example 2
assert sol.maxRequests([[1,1],[2,5],[1,2],[3,9]], 1, 1) == 3  # Example 3

assert sol.maxRequests([[1,1]], 1, 10) == 1  # Single request
assert sol.maxRequests([[1,1],[1,1],[1,1]], 1, 5) == 1  # Same timestamp
assert sol.maxRequests([[1,1],[1,1],[1,1]], 2, 5) == 2  # Keep up to k
assert sol.maxRequests([[1,1],[1,10],[1,20]], 1, 5) == 3  # No overlap

assert sol.maxRequests([[1,1],[1,2],[1,3],[1,4]], 2, 100) == 2  # Huge window

assert sol.maxRequests(
    [[1,1],[1,2],[2,1],[2,2]],
    1,
    1
) == 2  # Independent users

assert sol.maxRequests(
    [[1,1],[1,2],[1,3],[1,4],[1,5]],
    2,
    2
) == 4  # Sliding window interaction

assert sol.maxRequests(
    [[1,1],[1,6],[1,11],[1,16]],
    1,
    4
) == 4  # Every request survives

assert sol.maxRequests(
    [[1,5],[1,5],[1,5],[1,5],[1,5]],
    3,
    10
) == 3  # Many duplicates

Test	Why
Example 1	Basic non-overlapping requests
Example 2	Multiple requests inside one window
Example 3	Inclusive boundary behavior
Single request	Smallest valid input
All timestamps equal, k=1	Maximum conflict
All timestamps equal, k=2	Duplicate timestamps with larger limit
Widely spaced timestamps	No removals needed
Huge window	Almost all requests overlap
Multiple users	Confirms independence between users
Sliding overlap case	Tests continuous window maintenance
All requests survive	Verifies no unnecessary removals
Many duplicates	Stress test for equal timestamps

Edge Cases

Multiple Requests at the Same Timestamp

Requests can share the exact same timestamp. Since the interval is inclusive, all of these requests belong to the same window. A common bug is to treat equal timestamps as separate windows or fail to count them together. The sliding window naturally handles this because all equal timestamps remain active simultaneously, allowing at most k of them to be kept.

Requests Exactly window Apart

If timestamps differ by exactly window, they still belong to the same valid interval. For example, with window = 4, timestamps 1 and 5 both lie in the interval [1, 5]. The implementation removes timestamps only when:

active[0] < t - window

not when they are equal. This correctly preserves the inclusive boundary.

Very Large User Groups

One user may own nearly all 100,000 requests. A naive solution that repeatedly scans previous requests would become quadratic. The deque-based sliding window ensures that each timestamp is inserted and removed at most once, keeping processing linear after sorting.

Many Independent Users

The input may contain a large number of users with only one or two requests each. Since violations are completely user-specific, grouping by user guarantees that requests from one user never interfere with another. The algorithm naturally handles this by processing each user's timeline independently.

Large Window Covering Nearly Everything

When window is very large, almost every request for a user may belong to the same active interval. In such cases, the answer for that user is simply capped at k. The greedy algorithm correctly reaches this result because once the active queue reaches size k, all additional requests are rejected until older ones eventually expire.