Maximum requests without violating the limit

Array Hash Table Greedy Sliding Window Sorting

66.6% acceptance

Apr 3, 2026

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_requests(requests: Vec<Vec<i32>>, k: i32, window: i32) -> i32 {
    let mut requests_by_user: std::collections::HashMap<i32, Vec<i32>> = std::collections::HashMap::new();

    for request in requests {
      requests_by_user.entry(request[0]).or_default().push(request[1]);
    }

    let limit = k as usize;
    let mut kept_total = 0i32;

    for times in requests_by_user.values_mut() {
      times.sort_unstable();

      let mut kept_times = Vec::with_capacity(times.len());
      let mut left = 0usize;

      for &time in times.iter() {
        while left < kept_times.len() && kept_times[left] < time - window {
          left += 1;
        }

        if kept_times.len() - left < limit {
          kept_times.push(time);
        }
      }

      kept_total += kept_times.len() as i32;
    }

    kept_total
  }
}