3851. Maximum Requests Without Violating the Limit 🔒

Description

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⁵

Solutions

Solution 1: Sliding Window + Deque

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 $\textit{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 $\textit{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.

class Solution {
    public int maxRequests(int[][] requests, int k, int window) {
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int[] r : requests) {
            int u = r[0], t = r[1];
            g.computeIfAbsent(u, x -> new ArrayList<>()).add(t);
        }

        int ans = requests.length;
        ArrayDeque<Integer> kept = new ArrayDeque<>();

        for (List<Integer> ts : g.values()) {
            Collections.sort(ts);
            kept.clear();
            for (int t : ts) {
                while (!kept.isEmpty() && t - kept.peekFirst() > window) {
                    kept.pollFirst();
                }
                if (kept.size() < k) {
                    kept.addLast(t);
                } else {
                    --ans;
                }
            }
        }
        return ans;
    }
}

class Solution {
public:
    int maxRequests(vector<vector<int>>& requests, int k, int window) {
        unordered_map<int, vector<int>> g;
        for (auto& r : requests) {
            g[r[0]].push_back(r[1]);
        }

        int ans = requests.size();
        for (auto& [_, ts] : g) {
            sort(ts.begin(), ts.end());
            queue<int> kept;
            int deletions = 0;

            for (int t : ts) {
                while (!kept.empty() && t - kept.front() > window) {
                    kept.pop();
                }
                if (kept.size() < k) {
                    kept.push(t);
                } else {
                    ans--;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def maxRequests(self, requests: list[list[int]], k: int, window: int) -> int:
        g = defaultdict(list)
        for u, t in requests:
            g[u].append(t)
        ans = len(requests)
        for ts in g.values():
            ts.sort()
            kept = deque()
            for t in ts:
                while kept and t - kept[0] > window:
                    kept.popleft()
                if len(kept) < k:
                    kept.append(t)
                else:
                    ans -= 1
        return ans

func maxRequests(requests [][]int, k int, window int) int {
	g := make(map[int][]int)
	for _, r := range requests {
		u, t := r[0], r[1]
		g[u] = append(g[u], t)
	}
	ans := len(requests)
	for _, ts := range g {
		sort.Ints(ts)
		kept := make([]int, 0)
		for _, t := range ts {
			for len(kept) > 0 && t-kept[0] > window {
				kept = kept[1:]
			}
			if len(kept) < k {
				kept = append(kept, t)
			} else {
				ans--
			}
		}
	}
	return ans
}

function maxRequests(requests: number[][], k: number, window: number): number {
    const g = new Map<number, number[]>();
    for (const [u, t] of requests) {
        if (!g.has(u)) g.set(u, []);
        g.get(u)!.push(t);
    }
    let ans = requests.length;
    for (const ts of g.values()) {
        ts.sort((a, b) => a - b);
        const kept: number[] = [];
        let head = 0;
        for (const t of ts) {
            while (head < kept.length && t - kept[head] > window) {
                head++;
            }
            if (kept.length - head < k) {
                kept.push(t);
            } else {
                --ans;
            }
        }
    }
    return ans;
}

use std::collections::{HashMap, VecDeque};

impl Solution {
    pub fn max_requests(requests: Vec<Vec<i32>>, k: i32, window: i32) -> i32 {
        let mut g: HashMap<i32, Vec<i32>> = HashMap::new();
        for r in &requests {
            let u: i32 = r[0];
            let t: i32 = r[1];
            g.entry(u).or_insert_with(Vec::new).push(t);
        }

        let mut ans: i32 = requests.len() as i32;
        let mut kept: VecDeque<i32> = VecDeque::new();

        for ts in g.values_mut() {
            ts.sort();
            kept.clear();

            for &t in ts.iter() {
                while let Some(&front) = kept.front() {
                    if t - front > window {
                        kept.pop_front();
                    } else {
                        break;
                    }
                }

                if kept.len() < k as usize {
                    kept.push_back(t);
                } else {
                    ans -= 1;
                }
            }
        }

        ans
    }
}

3851 - Maximum Requests Without Violating the Limit

3851. Maximum Requests Without Violating the Limit 🔒

Description

Solutions

Solution 1: Sliding Window + Deque

All Problems

All Solutions

Welcome to Subscribe On Youtube

3851. Maximum Requests Without Violating the Limit 🔒

Description

Solutions

Solution 1: Sliding Window + Deque

All Problems

All Solutions