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 a0-indexed integer array arr of length queries.length where arr[i] represents the number of servers thatdid not receive any requests during the time interval [queries[i] - x, queries[i]].

Note that the time intervals are inclusive.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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 <= 10^5
  • 1 <= logs.length <= 10^5
  • 1 <= queries.length <= 10^5
  • logs[i].length == 2
  • 1 <= logs[i][0] <= n
  • 1 <= logs[i][1] <= 10^6
  • 1 <= x <= 10^5
  • x < queries[i] <= 10^6

Solution

Method 1 – Sliding Window with Hash Map

Intuition

The key idea is to use a sliding window over the sorted logs to efficiently count, for each query, which servers did not receive any requests in the interval [query - x, query]. By sorting both logs and queries, we can process all queries in a single pass using two pointers and a hash map to track the number of requests per server in the current window.

Approach

  1. Sort the logs by time and queries by value, keeping track of their original indices.
  2. Use two pointers (l and r) to maintain a window of logs within [query - x, query].
  3. Use a hash map (or array) to count the number of requests per server in the current window and a variable to track the number of active servers.
  4. For each query:
    • Move r forward to include logs with time ≤ query.
    • Move l forward to exclude logs with time < query - x.
    • The number of servers with zero requests is n - active_servers.
  5. Restore the answer to the original query order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
        sort(logs.begin(), logs.end(), [](auto& a, auto& b) { return a[1] < b[1]; });
        vector<pair<int, int>> qs;
        for (int i = 0; i < queries.size(); ++i) qs.push_back({queries[i], i});
        sort(qs.begin(), qs.end());
        vector<int> cnt(n+1, 0), ans(queries.size());
        int l = 0, r = 0, active = 0;
        for (auto& [q, idx] : qs) {
            while (r < logs.size() && logs[r][1] <= q) {
                int id = logs[r][0];
                if (++cnt[id] == 1) ++active;
                ++r;
            }
            while (l < logs.size() && logs[l][1] < q - x) {
                int id = logs[l][0];
                if (--cnt[id] == 0) --active;
                ++l;
            }
            ans[idx] = n - active;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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] })
    type pair struct{ val, idx int }
    qs := make([]pair, len(queries))
    for i, q := range queries {
        qs[i] = pair{q, i}
    }
    sort.Slice(qs, func(i, j int) bool { return qs[i].val < qs[j].val })
    cnt := make([]int, n+1)
    ans := make([]int, len(queries))
    l, r, active := 0, 0, 0
    for _, q := range qs {
        for r < len(logs) && logs[r][1] <= q.val {
            id := logs[r][0]
            cnt[id]++
            if cnt[id] == 1 {
                active++
            }
            r++
        }
        for l < len(logs) && logs[l][1] < q.val-x {
            id := logs[l][0]
            cnt[id]--
            if cnt[id] == 0 {
                active--
            }
            l++
        }
        ans[q.idx] = n - active
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public int[] countServers(int n, int[][] logs, int x, int[] queries) {
        Arrays.sort(logs, Comparator.comparingInt(a -> a[1]));
        int m = queries.length;
        int[][] qs = new int[m][2];
        for (int i = 0; i < m; i++) {
            qs[i][0] = queries[i];
            qs[i][1] = i;
        }
        Arrays.sort(qs, Comparator.comparingInt(a -> a[0]));
        int[] cnt = new int[n+1];
        int[] ans = new int[m];
        int l = 0, r = 0, active = 0;
        for (int[] q : qs) {
            int query = q[0], idx = q[1];
            while (r < logs.length && logs[r][1] <= query) {
                int id = logs[r][0];
                if (++cnt[id] == 1) active++;
                r++;
            }
            while (l < logs.length && logs[l][1] < query - x) {
                int id = logs[l][0];
                if (--cnt[id] == 0) active--;
                l++;
            }
            ans[idx] = n - active;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun countServers(n: Int, logs: Array<IntArray>, x: Int, queries: IntArray): IntArray {
        logs.sortBy { it[1] }
        val qs = queries.mapIndexed { i, q -> q to i }.sortedBy { it.first }
        val cnt = IntArray(n+1)
        val ans = IntArray(queries.size)
        var l = 0; var r = 0; var active = 0
        for ((q, idx) in qs) {
            while (r < logs.size && logs[r][1] <= q) {
                val id = logs[r][0]
                if (++cnt[id] == 1) active++
                r++
            }
            while (l < logs.size && logs[l][1] < q - x) {
                val id = logs[l][0]
                if (--cnt[id] == 0) active--
                l++
            }
            ans[idx] = n - active
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def countServers(self, n: int, logs: list[list[int]], x: int, queries: list[int]) -> list[int]:
        logs.sort(key=lambda a: a[1])
        qs = sorted([(q, i) for i, q in enumerate(queries)])
        cnt = [0] * (n+1)
        ans = [0] * len(queries)
        l = r = active = 0
        for q, idx in qs:
            while r < len(logs) and logs[r][1] <= q:
                id = logs[r][0]
                cnt[id] += 1
                if cnt[id] == 1:
                    active += 1
                r += 1
            while l < len(logs) and logs[l][1] < q - x:
                id = logs[l][0]
                cnt[id] -= 1
                if cnt[id] == 0:
                    active -= 1
                l += 1
            ans[idx] = n - active
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

impl Solution {
    pub fn count_servers(n: i32, logs: Vec<Vec<i32>>, x: i32, queries: Vec<i32>) -> Vec<i32> {
        let mut logs = logs;
        logs.sort_by_key(|a| a[1]);
        let mut qs: Vec<(i32, usize)> = queries.iter().enumerate().map(|(i, &q)| (q, i)).collect();
        qs.sort();
        let mut cnt = vec![0; n as usize + 1];
        let mut ans = vec![0; queries.len()];
        let (mut l, mut r, mut active) = (0, 0, 0);
        for &(q, idx) in &qs {
            while r < logs.len() && logs[r][1] <= q {
                let id = logs[r][0] as usize;
                cnt[id] += 1;
                if cnt[id] == 1 {
                    active += 1;
                }
                r += 1;
            }
            while l < logs.len() && logs[l][1] < q - x {
                let id = logs[l][0] as usize;
                cnt[id] -= 1;
                if cnt[id] == 0 {
                    active -= 1;
                }
                l += 1;
            }
            ans[idx] = n - active;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    countServers(n: number, logs: number[][], x: number, queries: number[]): number[] {
        logs.sort((a, b) => a[1] - b[1]);
        const qs = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
        const cnt = Array(n+1).fill(0);
        const ans = Array(queries.length).fill(0);
        let l = 0, r = 0, active = 0;
        for (const [q, idx] of qs) {
            while (r < logs.length && logs[r][1] <= q) {
                const id = logs[r][0];
                cnt[id]++;
                if (cnt[id] === 1) active++;
                r++;
            }
            while (l < logs.length && logs[l][1] < q - x) {
                const id = logs[l][0];
                cnt[id]--;
                if (cnt[id] === 0) active--;
                l++;
            }
            ans[idx] = n - active;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O((L + Q) log L + L + Q + n), where L is the number of logs, Q is the number of queries, and n is the number of servers. Sorting dominates.
  • 🧺 Space complexity: O(n + Q), for the count array and answer array.