# Count Zero Request Servers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-zero-request-servers)
Canonical: https://scaleengineer.com/dsa/problems/count-zero-request-servers
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Honeywell](https://scaleengineer.com/companies/honeywell), [LTI](https://scaleengineer.com/companies/lti), [Zomato](https://scaleengineer.com/companies/zomato), [Flexport](https://scaleengineer.com/companies/flexport), [DP world](https://scaleengineer.com/companies/dp-world)
---
## 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 <= 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`

# Approaches
## Brute Force Iteration
This approach iterates through each query independently. For every query, it scans the entire `logs` array to identify which servers received requests within the specific time window `[query_time - x, query_time]`.
**Time:** O(Q * L), where `Q` is the number of queries and `L` is the number of logs. For each of the `Q` queries, we iterate through all `L` logs. This is highly inefficient and will likely result in a 'Time Limit Exceeded' error for large inputs. · **Space:** O(n), where `n` is the number of servers. In the worst case, for a single query, all `n` servers could be active, requiring the `HashSet` to store up to `n` elements.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient due to nested loops.; Does not scale for the given constraints and will time out.
### Explanation
The brute-force method is the most straightforward way to solve the problem. It directly translates the problem statement into code. For each query, it establishes a time interval and then checks every single log to see if it falls within that interval. A `HashSet` is used to efficiently store the unique IDs of servers that were active during the interval, preventing duplicate counting. The final answer for the query is the total number of servers minus the count of unique active servers. While simple, its performance degrades rapidly as the number of logs and queries increases, making it unsuitable for large datasets.

```java
class Solution {
    public int[] countServers(int n, int[][] logs, int x, int[] queries) {
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryTime = queries[i];
            int startTime = queryTime - x;
            int endTime = queryTime;
            Set<Integer> activeServers = new HashSet<>();
            for (int[] log : logs) {
                int serverId = log[0];
                int time = log[1];
                if (time >= startTime && time <= endTime) {
                    activeServers.add(serverId);
                }
            }
            result[i] = n - activeServers.size();
        }
        return result;
    }
}
```
### Algorithm
* Initialize an integer array `result` of the same size as `queries` to store the answers.
* Iterate through each query `q` at index `i` in the `queries` array.
* For each query, define the time window `[startTime, endTime]` as `[q - x, q]`.
* Create a `HashSet` called `activeServers` to keep track of the unique server IDs that received a request in this time window.
* Iterate through every `log` entry in the `logs` array.
* If a log's time `logTime` falls within `[startTime, endTime]`, add the `logServerId` to the `activeServers` set.
* After checking all logs, the number of active servers is the size of the `activeServers` set.
* The number of servers with zero requests is `n - activeServers.size()`.
* Store this count in `result[i]`.
* After processing all queries, return the `result` array.

## Sliding Window with Sorting
This is an optimized approach that avoids re-scanning logs for each query. By sorting both the `logs` (by time) and the `queries` (by time), we can use a sliding window technique. As we process queries in chronological order, the time window `[query_time - x, query_time]` slides forward. We can efficiently update the set of active servers by adding new logs that enter the window and removing old logs that exit it.
**Time:** O(L log L + Q log Q), where `L` is the number of logs and `Q` is the number of queries. The complexity is dominated by sorting the `logs` array (O(L log L)) and the `queries` array (O(Q log Q)). The subsequent sliding window traversal takes O(L + Q) time because each log is visited at most twice (by the `left` and `right` pointers). · **Space:** O(n + Q). We need O(Q) space for `indexedQueries` and the `result` array. We also need O(n) space for the `serverRequestCounts` array.
**Pros:** Highly efficient and passes the given constraints.; Processes logs and queries in a single pass after sorting, avoiding redundant work.
**Cons:** More complex to implement than the brute-force approach.; Requires sorting, which adds an `n log n` factor to the complexity.
### Explanation
This efficient solution leverages the fact that if we process queries in order of time, their corresponding time windows also move forward in a predictable way. This allows for a 'sliding window' over the logs. First, we sort both logs and queries by time. We use two pointers, `left` and `right`, to maintain a window of logs that are relevant to the current query. As we move to the next query (which has a later time), we expand the window by moving the `right` pointer to include new logs and shrink it by moving the `left` pointer to discard logs that are now too old. A frequency map tracks the request count for each server within the window, allowing us to efficiently maintain a count of unique active servers. This avoids the O(L) scan per query, leading to a much better overall time complexity.

```java
class Solution {
    public int[] countServers(int n, int[][] logs, int x, int[] queries) {
        // Sort logs by time
        Arrays.sort(logs, (a, b) -> Integer.compare(a[1], b[1]));

        // Create indexed queries to retain original order
        int[][] indexedQueries = new int[queries.length][2];
        for (int i = 0; i < queries.length; i++) {
            indexedQueries[i][0] = queries[i];
            indexedQueries[i][1] = i;
        }

        // Sort queries by time
        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(a[0], b[0]));

        int[] result = new int[queries.length];
        int[] serverRequestCounts = new int[n + 1];
        int activeServerCount = 0;
        int left = 0, right = 0;

        for (int[] query : indexedQueries) {
            int queryTime = query[0];
            int originalIndex = query[1];
            int startTime = queryTime - x;

            // Expand window: Add logs with time <= queryTime
            while (right < logs.length && logs[right][1] <= queryTime) {
                int serverId = logs[right][0];
                if (serverRequestCounts[serverId] == 0) {
                    activeServerCount++;
                }
                serverRequestCounts[serverId]++;
                right++;
            }

            // Shrink window: Remove logs with time < startTime
            while (left < right && logs[left][1] < startTime) {
                int serverId = logs[left][0];
                serverRequestCounts[serverId]--;
                if (serverRequestCounts[serverId] == 0) {
                    activeServerCount--;
                }
                left++;
            }

            result[originalIndex] = n - activeServerCount;
        }

        return result;
    }
}
```
### Algorithm
* Create a 2D array `indexedQueries` where each element is `[query_time, original_index]` to preserve the original order of queries.
* Sort the `logs` array based on `time` in ascending order.
* Sort the `indexedQueries` array based on `query_time` in ascending order.
* Initialize a frequency map `serverRequestCounts` (e.g., an array of size `n+1`) and a counter `activeServerCount` to 0.
* Use two pointers, `left` and `right`, for the sorted `logs` array, both starting at 0.
* Iterate through the sorted `indexedQueries`.
* For each query `[q_time, original_idx]`:
    * a. **Expand Window:** Move the `right` pointer forward to include all logs with `time <= q_time`. For each new log, update `serverRequestCounts` and `activeServerCount`.
    * b. **Shrink Window:** Move the `left` pointer forward to exclude all logs with `time < q_time - x`. For each removed log, update `serverRequestCounts` and `activeServerCount`.
    * c. **Calculate Result:** The number of idle servers is `n - activeServerCount`. Store this in the result array at `original_idx`.
* Return the result array.

# Solutions
### Java

```java
class Solution {
public
  int[] countServers(int n, int[][] logs, int x, int[] queries) {
    Arrays.sort(logs, (a, b)->a[1] - b[1]);
    int m = queries.length;
    int[][] qs = new int[m][0];
    for (int i = 0; i < m; ++i) {
      qs[i] = new int[]{queries[i], i};
    }
    Arrays.sort(qs, (a, b)->a[0] - b[0]);
    Map<Integer, Integer> cnt = new HashMap<>();
    int[] ans = new int[m];
    int j = 0, k = 0;
    for (var q : qs) {
      int r = q[0], i = q[1];
      int l = r - x;
      while (k < logs.length && logs[k][1] <= r) {
        cnt.merge(logs[k++][0], 1, Integer : : sum);
      }
      while (j < logs.length && logs[j][1] < l) {
        if (cnt.merge(logs[j][0], -1, Integer : : sum) == 0) {
          cnt.remove(logs[j][0]);
        }
        j++;
      }
      ans[i] = n - cnt.size();
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> countServers(int n, vector<vector<int>> &logs, int x,
                           vector<int> &queries) {
    sort(logs.begin(), logs.end(),
         [](const auto &a, const auto &b) { return a[1] < b[1]; });
    int m = queries.size();
    vector<pair<int, int>> qs(m);
    for (int i = 0; i < m; ++i) {
      qs[i] = {queries[i], i};
    }
    sort(qs.begin(), qs.end());
    unordered_map<int, int> cnt;
    vector<int> ans(m);
    int j = 0, k = 0;
    for (auto &[r, i] : qs) {
      int l = r - x;
      while (k < logs.size() && logs[k][1] <= r) {
        ++cnt[logs[k++][0]];
      }
      while (j < logs.size() && logs[j][1] < l) {
        if (--cnt[logs[j][0]] == 0) {
          cnt.erase(logs[j][0]);
        }
        ++j;
      }
      ans[i] = n - cnt.size();
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]: cnt = Counter() logs . sort(key=lambda x: x[1]) ans = [0] * len(queries) j = k = 0 for r, i in sorted(zip(queries, count())): l = r - x while k < len(logs) and logs[k][1] <= r: cnt[logs[k][0]] += 1 k += 1 while j < len(logs) and logs[j][1] < l: cnt[logs[j][0]] -= 1 if cnt[logs[j][0]] == 0: cnt . pop(logs[j][0]) j += 1 ans[i] = n - len(cnt) return ans

```