LeetCode 2747. Count Zero Request Servers Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: 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 × log l + m × 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.

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

func countServers(n int, logs [][]int, x int, queries []int) []int { sort.Slice(logs, func(i, j int) bool { return logs[i][1] < logs[j][1] }) m := len(queries) qs := make([][2]int, m) for i, q := range queries { qs[i] = [2]int{q, i} } sort.Slice(qs, func(i, j int) bool { return qs[i][0] < qs[j][0] }) cnt := map[int]int{} ans := make([]int, m) j, k := 0, 0 for _, q := range qs { r, i := q[0], q[1] l := r - x for k < len(logs) && logs[k][1] <= r { cnt[logs[k][0]]++ k++ } for j < len(logs) && logs[j][1] < l { cnt[logs[j][0]]-- if cnt[logs[j][0]] == 0 { delete(cnt, logs[j][0]) } j++ } ans[i] = n - len(cnt) } return ans }(code-box)

function countServers(n: number, logs: number[][], x: number, queries: number[]): number[] { logs.sort((a, b) => a[1] - b[1]); const m = queries.length; const qs: number[][] = []; for (let i = 0; i < m; ++i) { qs.push([queries[i], i]); } qs.sort((a, b) => a[0] - b[0]); const cnt: Map<number, number> = new Map(); const ans: number[] = new Array(m); let j = 0; let k = 0; for (const [r, i] of qs) { const l = r - x; while (k < logs.length && logs[k][1] <= r) { cnt.set(logs[k][0], (cnt.get(logs[k][0]) || 0) + 1); ++k; } while (j < logs.length && logs[j][1] < l) { cnt.set(logs[j][0], (cnt.get(logs[j][0]) || 0) - 1); if (cnt.get(logs[j][0]) === 0) { cnt.delete(logs[j][0]); } ++j; } ans[i] = n - cnt.size; } return ans; }(code-box)