Scale Engineer

Count Zero Request Servers

Med
#2472Time: 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.5 companies
Patterns
Sliding Window
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
HoneywellLTIZomatoFlexport

Prompt

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

2 approaches with complexity analysis and trade-offs.

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].

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.

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Very inefficient due to nested loops.

  • Does not scale for the given constraints and will time out.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem