Count Zero Request Servers
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer n denoting the total number of servers and a 2D
0-indexed integer array logs, where logs[i] = [server_id, time]
denotes that the server with id server_id received a request at time time.
You are also given an integer x and a 0-indexed integer array queries.
Return a0-indexed integer array arr of length queries.length
where arr[i] represents the number of servers thatdid not receive any requests during the time interval [queries[i] - x, queries[i]].
Note that the time intervals are inclusive.
Examples
Example 1
Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
Output: [1,2]
Explanation:
For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5, 10]. Hence, only server 3 gets zero requests.
For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.
Example 2
Input: n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
Output: [0,1]
Explanation:
For queries[0]: All servers get at least one request in the duration of [1, 3].
For queries[1]: Only server with id 3 gets no request in the duration [2,4].
Constraints
1 <= n <= 10^51 <= logs.length <= 10^51 <= queries.length <= 10^5logs[i].length == 21 <= logs[i][0] <= n1 <= logs[i][1] <= 10^61 <= x <= 10^5x < queries[i] <= 10^6
Solution
Method 1 – Sliding Window with Hash Map
Intuition
The key idea is to use a sliding window over the sorted logs to efficiently count, for each query, which servers did not receive any requests in the interval [query - x, query]. By sorting both logs and queries, we can process all queries in a single pass using two pointers and a hash map to track the number of requests per server in the current window.
Approach
- Sort the logs by time and queries by value, keeping track of their original indices.
- Use two pointers (
landr) to maintain a window of logs within[query - x, query]. - Use a hash map (or array) to count the number of requests per server in the current window and a variable to track the number of active servers.
- For each query:
- Move
rforward to include logs with time ≤ query. - Move
lforward to exclude logs with time < query - x. - The number of servers with zero requests is
n - active_servers.
- Move
- Restore the answer to the original query order.
Code
C++
class Solution {
public:
vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
sort(logs.begin(), logs.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
vector<pair<int, int>> qs;
for (int i = 0; i < queries.size(); ++i) qs.push_back({queries[i], i});
sort(qs.begin(), qs.end());
vector<int> cnt(n+1, 0), ans(queries.size());
int l = 0, r = 0, active = 0;
for (auto& [q, idx] : qs) {
while (r < logs.size() && logs[r][1] <= q) {
int id = logs[r][0];
if (++cnt[id] == 1) ++active;
++r;
}
while (l < logs.size() && logs[l][1] < q - x) {
int id = logs[l][0];
if (--cnt[id] == 0) --active;
++l;
}
ans[idx] = n - active;
}
return ans;
}
};
Go
func countServers(n int, logs [][]int, x int, queries []int) []int {
sort.Slice(logs, func(i, j int) bool { return logs[i][1] < logs[j][1] })
type pair struct{ val, idx int }
qs := make([]pair, len(queries))
for i, q := range queries {
qs[i] = pair{q, i}
}
sort.Slice(qs, func(i, j int) bool { return qs[i].val < qs[j].val })
cnt := make([]int, n+1)
ans := make([]int, len(queries))
l, r, active := 0, 0, 0
for _, q := range qs {
for r < len(logs) && logs[r][1] <= q.val {
id := logs[r][0]
cnt[id]++
if cnt[id] == 1 {
active++
}
r++
}
for l < len(logs) && logs[l][1] < q.val-x {
id := logs[l][0]
cnt[id]--
if cnt[id] == 0 {
active--
}
l++
}
ans[q.idx] = n - active
}
return ans
}
Java
class Solution {
public int[] countServers(int n, int[][] logs, int x, int[] queries) {
Arrays.sort(logs, Comparator.comparingInt(a -> a[1]));
int m = queries.length;
int[][] qs = new int[m][2];
for (int i = 0; i < m; i++) {
qs[i][0] = queries[i];
qs[i][1] = i;
}
Arrays.sort(qs, Comparator.comparingInt(a -> a[0]));
int[] cnt = new int[n+1];
int[] ans = new int[m];
int l = 0, r = 0, active = 0;
for (int[] q : qs) {
int query = q[0], idx = q[1];
while (r < logs.length && logs[r][1] <= query) {
int id = logs[r][0];
if (++cnt[id] == 1) active++;
r++;
}
while (l < logs.length && logs[l][1] < query - x) {
int id = logs[l][0];
if (--cnt[id] == 0) active--;
l++;
}
ans[idx] = n - active;
}
return ans;
}
}
Kotlin
class Solution {
fun countServers(n: Int, logs: Array<IntArray>, x: Int, queries: IntArray): IntArray {
logs.sortBy { it[1] }
val qs = queries.mapIndexed { i, q -> q to i }.sortedBy { it.first }
val cnt = IntArray(n+1)
val ans = IntArray(queries.size)
var l = 0; var r = 0; var active = 0
for ((q, idx) in qs) {
while (r < logs.size && logs[r][1] <= q) {
val id = logs[r][0]
if (++cnt[id] == 1) active++
r++
}
while (l < logs.size && logs[l][1] < q - x) {
val id = logs[l][0]
if (--cnt[id] == 0) active--
l++
}
ans[idx] = n - active
}
return ans
}
}
Python
class Solution:
def countServers(self, n: int, logs: list[list[int]], x: int, queries: list[int]) -> list[int]:
logs.sort(key=lambda a: a[1])
qs = sorted([(q, i) for i, q in enumerate(queries)])
cnt = [0] * (n+1)
ans = [0] * len(queries)
l = r = active = 0
for q, idx in qs:
while r < len(logs) and logs[r][1] <= q:
id = logs[r][0]
cnt[id] += 1
if cnt[id] == 1:
active += 1
r += 1
while l < len(logs) and logs[l][1] < q - x:
id = logs[l][0]
cnt[id] -= 1
if cnt[id] == 0:
active -= 1
l += 1
ans[idx] = n - active
return ans
Rust
impl Solution {
pub fn count_servers(n: i32, logs: Vec<Vec<i32>>, x: i32, queries: Vec<i32>) -> Vec<i32> {
let mut logs = logs;
logs.sort_by_key(|a| a[1]);
let mut qs: Vec<(i32, usize)> = queries.iter().enumerate().map(|(i, &q)| (q, i)).collect();
qs.sort();
let mut cnt = vec![0; n as usize + 1];
let mut ans = vec![0; queries.len()];
let (mut l, mut r, mut active) = (0, 0, 0);
for &(q, idx) in &qs {
while r < logs.len() && logs[r][1] <= q {
let id = logs[r][0] as usize;
cnt[id] += 1;
if cnt[id] == 1 {
active += 1;
}
r += 1;
}
while l < logs.len() && logs[l][1] < q - x {
let id = logs[l][0] as usize;
cnt[id] -= 1;
if cnt[id] == 0 {
active -= 1;
}
l += 1;
}
ans[idx] = n - active;
}
ans
}
}
TypeScript
class Solution {
countServers(n: number, logs: number[][], x: number, queries: number[]): number[] {
logs.sort((a, b) => a[1] - b[1]);
const qs = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
const cnt = Array(n+1).fill(0);
const ans = Array(queries.length).fill(0);
let l = 0, r = 0, active = 0;
for (const [q, idx] of qs) {
while (r < logs.length && logs[r][1] <= q) {
const id = logs[r][0];
cnt[id]++;
if (cnt[id] === 1) active++;
r++;
}
while (l < logs.length && logs[l][1] < q - x) {
const id = logs[l][0];
cnt[id]--;
if (cnt[id] === 0) active--;
l++;
}
ans[idx] = n - active;
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O((L + Q) log L + L + Q + n), where L is the number of logs, Q is the number of queries, and n is the number of servers. Sorting dominates. - 🧺 Space complexity:
O(n + Q), for the count array and answer array.