Skip to main content
Talentd

Count Zero Request Servers - Solution & Explanation

MediumArrayHash TableSliding WindowSorting21 min readAsked at: Amazon, Honeywell, Rubrik +1
Practice this problem

Problem Statement

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 <= 105
  • 1 <= logs.length <= 105
  • 1 <= queries.length <= 105
  • logs[i].length == 2
  • 1 <= logs[i][0] <= n
  • 1 <= logs[i][1] <= 106
  • 1 <= x <= 105
  • x < 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

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.

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.
Space Complexity: O(n) for server states tracking.

Offline Queries + Sorting + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window with Sorted LogsO((m + q) log m)O(n)Best general solution when handling many queries efficiently
Binary Search + Scan WindowO(q log m + k)O(n)Useful when query count is small or log windows are short

Video Solution

Leetcode BiWeekly contest 107 - Medium - Count Zero Request Servers • Prakhar Agrawal • 1,666 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Count Zero Request Servers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays