2747. Count Zero Request Servers LeetCode Solution

In this guide, you will get 2747. Count Zero Request Servers LeetCode Solution with the best time and space complexity. The solution to Count Zero Request Servers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Zero Request Servers solution in C++
Count Zero Request Servers solution in Java
Count Zero Request Servers solution in Python
Additional Resources

2747. Count Zero Request Servers LeetCode Solution image

Problem Statement of Count Zero Request Servers

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

Complexity Analysis

Time Complexity: O(\texttt{sort}(n) + \texttt{sort}(q) + q\log n)
Space Complexity: O(n + q)

2747. Count Zero Request Servers LeetCode Solution in C++

struct IndexedQuery {
  int queryIndex;
  int query;
};

class Solution {
 public:
  vector<int> countServers(int n, vector<vector<int>>& logs, int x,
                           vector<int>& queries) {
    vector<int> ans(queries.size());
    vector<int> count(n + 1);

    ranges::sort(logs, ranges::less{},
                 [](const vector<int>& log) { return log[1]; });

    int i = 0;
    int j = 0;
    int servers = 0;

    // For each query, we care about logs[i..j].
    for (const auto& [queryIndex, query] : getIndexedQueries(queries)) {
      for (; j < logs.size() && logs[j][1] <= query; ++j)
        if (++count[logs[j][0]] == 1)
          ++servers;
      for (; i < logs.size() && logs[i][1] < query - x; ++i)
        if (--count[logs[i][0]] == 0)
          --servers;
      ans[queryIndex] = n - servers;
    }

    return ans;
  }

 private:
  vector<IndexedQuery> getIndexedQueries(const vector<int>& queries) {
    vector<IndexedQuery> indexedQueries;
    for (int i = 0; i < queries.size(); ++i)
      indexedQueries.push_back({i, queries[i]});
    ranges::sort(indexedQueries,
                 [](const IndexedQuery& a, const IndexedQuery& b) {
      return a.query < b.query;
    });
    return indexedQueries;
  }
};
/* code provided by PROGIEZ */

2747. Count Zero Request Servers LeetCode Solution in Java

class Solution {
  public int[] countServers(int n, int[][] logs, int x, int[] queries) {
    int[] ans = new int[queries.length];
    int[] count = new int[n + 1];

    Arrays.sort(logs, (a, b) -> Integer.compare(a[1], b[1]));

    int i = 0;
    int j = 0;
    int servers = 0;

    // For each query, we care about logs[i..j].
    for (IndexedQuery indexedQuery : getIndexedQueries(queries)) {
      final int queryIndex = indexedQuery.queryIndex;
      final int query = indexedQuery.query;
      for (; j < logs.length && logs[j][1] <= query; ++j)
        if (++count[logs[j][0]] == 1)
          ++servers;
      for (; i < logs.length && logs[i][1] < query - x; ++i)
        if (--count[logs[i][0]] == 0)
          --servers;
      ans[queryIndex] = n - servers;
    }

    return ans;
  }

  private record IndexedQuery(int queryIndex, int query){};

  private IndexedQuery[] getIndexedQueries(int[] queries) {
    IndexedQuery[] indexedQueries = new IndexedQuery[queries.length];
    for (int i = 0; i < queries.length; ++i)
      indexedQueries[i] = new IndexedQuery(i, queries[i]);
    Arrays.sort(indexedQueries, (a, b) -> Integer.compare(a.query, b.query));
    return indexedQueries;
  }
}
// code provided by PROGIEZ

2747. Count Zero Request Servers LeetCode Solution in Python

from dataclasses import dataclass


@dataclass(frozen=True)
class IndexedQuery:
  queryIndex: int
  query: int

  def __iter__(self):
    yield self.queryIndex
    yield self.query


class Solution:
  def countServers(
      self,
      n: int,
      logs: list[list[int]],
      x: int,
      queries: list[int],
  ) -> list[int]:
    ans = [0] * len(queries)
    count = [0] * (n + 1)

    logs.sort(key=lambda x: x[1])

    i = 0
    j = 0
    servers = 0

    # For each query, we care about logs[i..j].
    for queryIndex, query in sorted([IndexedQuery(i, query)
                                     for i, query in enumerate(queries)],
                                    key=lambda x: x.query):
      while j < len(logs) and logs[j][1] <= query:
        count[logs[j][0]] += 1
        if count[logs[j][0]] == 1:
          servers += 1
        j += 1
      while i < len(logs) and logs[i][1] < query - x:
        count[logs[i][0]] -= 1
        if count[logs[i][0]] == 0:
          servers -= 1
        i += 1
      ans[queryIndex] = n - servers

    return ans
 # code by PROGIEZ