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] <= 106Problem 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.
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.
This solution parses logs and maintains the number of active servers within the query window. Each query determines the number of logs relevant to the interval, computes the number of active servers, and deduces those with zero requests.
Time Complexity: O(M * N), where M is the number of queries and N is the number of log entries.
Space Complexity: O(n), where n is the total number of servers.
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.
This C solution orders log entries and utilizes a binary search (lower bound) to locate the earliest possible entry for each query. By leveraging two pointers post-binary search, it tracks active server logs within each time-frame.
Time Complexity: O(N log N) for sorting and O(M log N) for binary search work per query.
Space Complexity: O(n) for server states tracking.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(M * N), where M is the number of queries and N is the number of log entries. |
| Binary Search with Two-Pointer Technique | Time Complexity: O(N log N) for sorting and O(M log N) for binary search work per query. |
| Offline Queries + Sorting + Two Pointers | — |
| 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 |
Leetcode BiWeekly contest 107 - Medium - Count Zero Request Servers • Prakhar Agrawal • 1,639 views views
Watch 8 more video solutions →Practice Count Zero Request Servers with our built-in code editor and test cases.
Practice on FleetCode