Count Zero Request Servers solution and explanation
8 more videos on this problem
Leetcode BiWeekly contest 107 - Medium - Count Zero Request ServersPrakhar Agrawal · 14:40 · 1K views
Count Zero Request Servers | Leetcode 2747 | Sorting + Sliding WindowTech Courses · 17:42 · 1K views
Count Zero Request Servers - LeetCode 2747 - PythonAlpha-Code · 27:09 · 580 views
2747. Count Zero Request Servers (Leetcode Medium)Programming Live with Larry · 52:43 · 394 views
【每日一题】LeetCode 2747. Count Zero Request ServersHuifeng Guan · 12:10 · 391 views
Leetcode 2747. Count Zero Request Servers (offline query + sliding window)LetsCode · 30:53 · 246 views
Count Zero Request Servers (Leetcode Biweekly 107)Soumya Bhattacharjee · 8:36 · 163 views
D: Leetcode biweekly contest 107 Count Zero Request Servers Problem Solution || 24th June 2023Kadupul Dev Tube · 3:19 · 111 views
Fail Leetcode #2747 Count Zero Request ServersPass OR Fail: Coding Journey · 1:29:30 · 16 views
The 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 a 0-indexed integer array arr of length queries.length where arr[i] represents the number of servers that did not receive any requests during the time interval [queries[i] - x, queries[i]].
Note that the time intervals are inclusive.
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 <= 1051 <= logs.length <= 1051 <= queries.length <= 105logs[i].length == 21 <= logs[i][0] <= n1 <= logs[i][1] <= 1061 <= x <= 105x < queries[i] <= 106
Approach overview
Problem Overview: You are given n servers and a list of request logs where each log contains [server_id, time]. For every query time q, count how many servers received zero requests in the time window [q - x, q]. The challenge is efficiently tracking which servers were active inside each window while handling many queries.
Approach 1: Sliding Window with Sorting (O((m + q) log m) time, O(n) space)
Sort the request logs by timestamp and also sort queries while keeping their original indices. Maintain a sliding window over the logs representing the active time range [query - x, query]. Use two pointers to expand the right boundary for logs with time ≤ query and shrink the left boundary when time < query - x. Track how many requests each server has inside the window using a frequency array or hash map. When a server’s count transitions from 0→1 it becomes active; when it drops to 0 it becomes inactive. The number of zero-request servers is simply n - active_servers. This approach works well because each log enters and leaves the window at most once.
This technique relies heavily on concepts from sliding window and sorting. The logs are processed sequentially while the window dynamically adapts to each query time.
Approach 2: Binary Search with Two-Pointer Technique (O(q log m + k) time, O(n) space)
Another option is preprocessing the logs by sorting them by timestamp. For each query, use binary search to locate the first log with time ≥ query - x and the last log with time ≤ query. This gives the subarray of logs inside the window. Then iterate through this range and track which servers appear using a hash table or boolean array. The number of servers not seen in this range equals the result for that query.
The key idea is leveraging binary search to quickly isolate the relevant log segment. However, repeatedly scanning the segment for each query can be expensive when many logs fall in the window. Compared to the sliding window solution, this approach is simpler conceptually but less efficient for dense log distributions.
Core concepts include arrays, hash tables, and binary search over sorted timestamps.
Recommended for interviews: The sliding window approach is the expected solution. It processes logs and queries in sorted order and ensures each log is added and removed from the window exactly once. Interviewers typically want to see you recognize the time-window pattern and apply two pointers with a frequency structure to maintain active servers efficiently.
Approach 1: Sliding Window Approach
This approach utilizes a sliding window to efficiently track servers that receive requests within specified time intervals. By maintaining an active set of server logs that fall within the window, we can easily determine which servers did not receive requests during each query window.
def count_zero_request_servers(n, logs, x, queries):
logs.sort(key=lambda log: log[1])
results = []
for query in queries:
start = query - x
end = query
active_servers = set()
for server, time in logs:
if time > end:
break
if start <= time <= end:
active_servers.add(server)
results.append(n - len(active_servers))
return resultsimport java.util.*;
public class ZeroRequestServers {
public int[] countZeroRequestServers(int n, int[][] logs, int x, int[] queries) {
Arrays.sort(logs, Comparator.comparingInt(a -> a[1]));
int[] result = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int start = queries[q] - x;
int end = queries[q];
Set<Integer> activeServers = new HashSet<>();
for (int[] log : logs) {
if (log[1] > end) break;
if (log[1] >= start && log[1] <= end) {
activeServers.add(log[0]);
}
}
result[q] = n - activeServers.size();
}
return result;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<int> countZeroRequestServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
vector<int> result(queries.size());
sort(logs.begin(), logs.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
for (int q = 0; q < queries.size(); ++q) {
int start = queries[q] - x;
int end = queries[q];
vector<int> activeServers(n + 1, 0);
int countActiveLogs = 0;
for (auto& log : logs) {
if (log[1] > end) break;
if (log[1] >= start && log[1] <= end) {
if (!activeServers[log[0]]) {
countActiveLogs++;
activeServers[log[0]] = 1;
}
}
}
result[q] = n - countActiveLogs;
}
return result;
}function countZeroRequestServers(n, logs, x, queries) {
logs.sort((a, b) => a[1] - b[1]);
const result = Array(queries.length).fill(0);
for (let q = 0; q < queries.length; q++) {
const start = queries[q] - x;
const end = queries[q];
const activeServers = new Set();
for (const [server, time] of logs) {
if (time > end) break;
if (time >= start && time <= end) {
activeServers.add(server);
}
}
result[q] = n - activeServers.size;
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void *a, const void *b) {
return (*(int **)a)[1] - (*(int **)b)[1];
}
int* countZeroRequestServers(int n, int** logs, int logsSize, int* logsColSize, int x, int* queries, int queriesSize, int* returnSize) {
int* result = (int*) malloc(sizeof(int) * queriesSize);
*returnSize = queriesSize;
qsort(logs, logsSize, sizeof(logs[0]), cmpfunc);
for (int q = 0; q < queriesSize; q++) {
int countActiveLogs = 0;
int start = queries[q] - x;
int end = queries[q];
int* activeServers = (int*) calloc(n + 1, sizeof(int));
for (int i = 0; i < logsSize; i++) {
int serverId = logs[i][0];
int logTime = logs[i][1];
if (logTime > end) break;
if (logTime >= start && logTime <= end) {
if (!activeServers[serverId]) {
countActiveLogs++;
activeServers[serverId] = 1;
}
}
}
result[q] = n - countActiveLogs;
free(activeServers);
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] CountZeroRequestServers(int n, int[][] logs, int x, int[] queries) {
Array.Sort(logs, (a, b) => a[1].CompareTo(b[1]));
int[] result = new int[queries.Length];
for (int q = 0; q < queries.Length; q++) {
int start = queries[q] - x;
int end = queries[q];
HashSet<int> activeServers = new HashSet<int>();
foreach (var log in logs) {
if (log[1] > end) break;
if (log[1] >= start && log[1] <= end) {
activeServers.Add(log[0]);
}
}
result[q] = n - activeServers.Count;
}
return result;
}
}This solution sorts the logs based on time and iteratively checks each query's window using a set to maintain active servers, resulting in a list of the number of servers receiving no requests.
Time Complexity: O(M * N).
Space Complexity: O(n), where n is the distinct servers active in the window.
Approach 2: Binary Search with Two-Pointer Technique
This approach applies binary search to more efficiently narrow down the relevant logs for each query. By engaging a two-pointer technique along with sorting, it reduces unnecessary iterations over irrelevant logs. The key idea is to use binary search for filtering outbound logs initially, then apply two pointers for server activity counting within the acceptable window.
from bisect import bisect_left
def count_zero_request_servers(n, logs, x, queries):
logs.sort(key=lambda log: log[1])
results = []
for query in queries:
start = query - x
end = query
lb = bisect_left(logs, [0, start], key=lambda log: log[1])
active_servers = set()
for server, time in logs[lb:]:
if time > end:
break
active_servers.add(server)
results.append(n - len(active_servers))
return resultsimport java.util.*;
public class ZeroRequestServers {
public int[] countZeroRequestServers(int n, int[][] logs, int x, int[] queries) {
Arrays.sort(logs, Comparator.comparingInt(a -> a[1]));
int[] result = new int[queries.length];
for (int q = 0; q < queries.length; q++) {
int start = queries[q] - x;
int end = queries[q];
int lb = lowerBound(logs, start);
Set<Integer> activeServers = new HashSet<>();
for (int i = lb; i < logs.length && logs[i][1] <= end; i++) {
activeServers.add(logs[i][0]);
}
result[q] = n - activeServers.size();
}
return result;
}
private int lowerBound(int[][] logs, int target) {
int left = 0, right = logs.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (logs[mid][1] >= target) right = mid;
else left = mid + 1;
}
return left;
}
}#include <vector>
#include <algorithm>
using namespace std;
int lowerBound(vector<vector<int>>& logs, int target) {
return lower_bound(logs.begin(), logs.end(), vector<int>{0, target}, [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
}) - logs.begin();
}
vector<int> countZeroRequestServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
vector<int> result(queries.size());
sort(logs.begin(), logs.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
for (int q = 0; q < queries.size(); ++q) {
int start = queries[q] - x;
int end = queries[q];
int lb = lowerBound(logs, start);
vector<int> activeServers(n + 1, 0);
int countActiveLogs = 0;
for (int i = lb; i < logs.size() && logs[i][1] <= end; ++i) {
if (!activeServers[logs[i][0]]) {
countActiveLogs++;
activeServers[logs[i][0]] = 1;
}
}
result[q] = n - countActiveLogs;
}
return result;
}function countZeroRequestServers(n, logs, x, queries) {
logs.sort((a, b) => a[1] - b[1]);
const result = queries.map(query => {
const start = query - x;
const end = query;
const index = logs.findIndex(([_, time]) => time >= start);
const activeServers = new Set();
for (let i = index; i < logs.length; i++) {
const [server, time] = logs[i];
if (time > end) break;
activeServers.add(server);
}
return n - activeServers.size;
});
return result;
}#include <stdio.h>
#include <stdlib.h>
int cmpfunc(const void *a, const void *b) {
return (*(int **)a)[1] - (*(int **)b)[1];
}
int lowerBound(int** logs, int logsSize, int target) {
int start = 0, end = logsSize;
while (start < end) {
int mid = start + (end - start) / 2;
if (logs[mid][1] >= target) end = mid;
else start = mid + 1;
}
return start;
}
int* countZeroRequestServers(int n, int** logs, int logsSize, int* logsColSize, int x, int* queries, int queriesSize, int* returnSize) {
int* result = (int*) malloc(sizeof(int) * queriesSize);
*returnSize = queriesSize;
qsort(logs, logsSize, sizeof(logs[0]), cmpfunc);
for (int q = 0; q < queriesSize; q++) {
int countActiveLogs = 0;
int start = queries[q] - x;
int end = queries[q];
int lb = lowerBound(logs, logsSize, start);
int* activeServers = (int*) calloc(n + 1, sizeof(int));
for (int i = lb; i < logsSize && logs[i][1] <= end; i++) {
int serverId = logs[i][0];
if (!activeServers[serverId]) {
countActiveLogs++;
activeServers[serverId] = 1;
}
}
result[q] = n - countActiveLogs;
free(activeServers);
}
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] CountZeroRequestServers(int n, int[][] logs, int x, int[] queries) {
Array.Sort(logs, (a, b) => a[1].CompareTo(b[1]));
int[] result = new int[queries.Length];
for (int q = 0; q < queries.Length; q++) {
int start = queries[q] - x;
int end = queries[q];
int lb = Array.BinarySearch(logs, new int[] {0, start}, (a, b) => a[1].CompareTo(b[1]));
if (lb < 0) lb = ~lb;
HashSet<int> activeServers = new HashSet<int>();
for (int i = lb; i < logs.Length && logs[i][1] <= end; i++) {
activeServers.Add(logs[i][0]);
}
result[q] = n - activeServers.Count;
}
return result;
}
}Python solution employs sorting, a binary search via bisect for lower bounds, and then iterates using a set to track server log activity comprehensively.
Time Complexity: O(N log N) for sorting, plus O(M log N) due to bisect checks per query.
Space Complexity: O(n).
Approach 3: Offline Queries + Sorting + Two Pointers
We can sort all the queries by time from smallest to largest, and then process each query in chronological order.
For each query q = (r, i), its window left boundary is l = r - x, and we need to count how many servers received requests within the window [l, r]. We use two pointers j and k to maintain the left and right boundaries of the window, initially j = k = 0. Each time, if the log time pointed by k is less than or equal to r, we add it to the window, and then move k to the right by one. If the log time pointed by j is less than l, we remove it from the window, and then move j to the right by one. During the movement, we need to count how many different servers are in the window, which can be implemented using a hash table. After the movement, the number of servers that did not receive requests in the current time interval is n minus the number of different servers in the hash table.
The time complexity is O(l times log l + m times log m + n), and the space complexity is O(l + m). Here, l and n are the lengths of the arrays logs and the number of servers, respectively, while m is the length of the array queries.
function countServers(n: number, logs: number[][], x: number, queries: number[]): number[] {
logs.sort((a, b) => a[1] - b[1]);
const m = queries.length;
const qs: number[][] = [];
for (let i = 0; i < m; ++i) {
qs.push([queries[i], i]);
}
qs.sort((a, b) => a[0] - b[0]);
const cnt: Map<number, number> = new Map();
const ans: number[] = new Array(m);
let j = 0;
let k = 0;
for (const [r, i] of qs) {
const l = r - x;
while (k < logs.length && logs[k][1] <= r) {
cnt.set(logs[k][0], (cnt.get(logs[k][0]) || 0) + 1);
++k;
}
while (j < logs.length && logs[j][1] < l) {
cnt.set(logs[j][0], (cnt.get(logs[j][0]) || 0) - 1);
if (cnt.get(logs[j][0]) === 0) {
cnt.delete(logs[j][0]);
}
++j;
}
ans[i] = n - cnt.size;
}
return ans;
}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] })
m := len(queries)
qs := make([][2]int, m)
for i, q := range queries {
qs[i] = [2]int{q, i}
}
sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] })
cnt := map[int]int{}
ans := make([]int, m)
j, k := 0, 0
for _, q := range qs {
r, i := q[0], q[1]
l := r - x
for k < len(logs) && logs[k][1] <= r {
cnt[logs[k][0]]++
k++
}
for j < len(logs) && logs[j][1] < l {
cnt[logs[j][0]]--
if cnt[logs[j][0]] == 0 {
delete(cnt, logs[j][0])
}
j++
}
ans[i] = n - len(cnt)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(M * N). |
| Binary Search with Two-Pointer Technique | Time Complexity: O(N log N) for sorting, plus O(M log N) due to bisect checks per query. |
| Offline Queries + Sorting + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with Sorted Logs | O((m + q) log m) | O(n) | Best general solution when handling many queries efficiently |
| Binary Search + Scan Window | O(q log m + k) | O(n) | Useful when query count is small or log windows are short |
Frequently asked questions
Is Count Zero Request Servers easy or hard?
Count Zero Request Servers is rated Medium difficulty. The challenge is recognizing that queries represent time windows and designing an efficient sliding window solution instead of recomputing results for each query independently.
Count Zero Request Servers Python/Java solution
Python and Java implementations typically sort logs and queries, then apply a sliding window with two pointers. A list or HashMap stores request counts per server, and a variable tracks how many servers currently have at least one request in the window. Each query result is computed as n minus the active server count.
How to solve Count Zero Request Servers in O(n)?
After sorting logs and queries by time, maintain a sliding window using two pointers over the logs. Expand the right pointer while log times are ≤ query and shrink the left pointer when logs fall before query - x. Track server request counts with an array or hash table and compute zero-request servers as n minus the number of active servers.
What is the best approach for Count Zero Request Servers?
The sliding window approach after sorting logs and queries is the most efficient solution. It maintains a dynamic window of logs within [query - x, query] using two pointers and tracks active servers with a frequency array or hash map. Each log enters and leaves the window once, giving near linear processing after sorting.
Is Count Zero Request Servers asked at Google/Amazon/Meta?
Problems involving time-window queries, sliding windows, and log processing frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test the ability to combine sorting, two pointers, and hash-based counting for efficient event window tracking.
What data structure is used in Count Zero Request Servers?
The main structures are arrays or hash tables to track how many requests each server has within the current window. Combined with sorted arrays of logs and queries, these structures allow constant-time updates when logs enter or leave the sliding window.
What is the time complexity of Count Zero Request Servers?
The optimal sliding window solution runs in O((m + q) log m) time due to sorting the logs and queries, where m is the number of logs and q is the number of queries. After sorting, the window operations are linear because each log is processed at most twice. Space complexity is O(n) for tracking active server counts.