2747. Count Zero Request Servers
- Array
- Hash Table
- Sliding Window
- Sorting
TIME
O(m log m + q log q + n)
SPACE
O(n + m + q)
Intuition
Each query asks how many distinct servers appear in the time window [q - x, q], and the answer is n minus that. Handled one by one, each query would scan the logs. But every window has the same length, so if the queries are answered in increasing order, each window's start and end only move right. One sliding window over the sorted logs can answer all of them, as long as the results go back to each query's original position.
Approach
- Sort the logs by time, and sort the query indices by query value.
- Keep
count[server]for requests inside the window, andactive, the number of servers with a non-zero count. - For each query
qin sorted order:- add logs with
time <= q, raisingactivewhen a count goes from 0 to 1; - remove logs with
time < q - x, loweringactivewhen a count goes from 1 to 0; - store
n - activeat the query's original index.
- add logs with
Every log with time < q - x also has time <= q, so it has already been added and the left pointer can't pass the right one.
Complexity
- Time: O(m log m + q log q + n), where
m = len(logs)andq = len(queries). Each log is added and removed at most once - Space: O(n + m + q)
Edge Cases
- Both ends of the interval are inclusive:
time == q - xandtime == qboth count, which is why removal uses<and addition uses<= - A server with several requests in the window must count once, which is why
activechanges only on the 0 and 1 transitions - No logs in the window: the answer is
n - Duplicate query values get the same answer and keep their own positions
- Query order differs from input order: answers are written back by original index
- Server ids are 1-based, so
counthas sizen + 1 - A log later than every query is never added
Code
from typing import List
class Solution:
def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
"""
2747. Count Zero Request Servers
Time: O(m log m + q log q + n)
Space: O(n + m + q)
"""
logs = sorted(logs, key=lambda log: log[1])
m = len(logs)
count = [0] * (n + 1) # server ids are 1-based
active = left = right = 0
answer = [0] * len(queries)
# Answer queries in increasing order so the window only moves right.
for i in sorted(range(len(queries)), key=queries.__getitem__):
q = queries[i]
while right < m and logs[right][1] <= q:
server = logs[right][0]
if count[server] == 0:
active += 1
count[server] += 1
right += 1
while left < right and logs[left][1] < q - x:
server = logs[left][0]
count[server] -= 1
if count[server] == 0:
active -= 1
left += 1
answer[i] = n - active
return answerimport java.util.*;
/**
* 2747. Count Zero Request Servers
* Time: O(m log m + q log q + n)
* Space: O(n + m + q)
*/
class Solution {
private static final int BITS = 17; // ids and indices are at most 10^5 < 2^17
private static final long MASK = (1L << BITS) - 1;
public int[] countServers(int n, int[][] logs, int x, int[] queries) {
int m = logs.length, k = queries.length;
// Pack (time, server) and (query, index) into longs so both sort
// without boxing or changing the input.
long[] byTime = new long[m];
for (int i = 0; i < m; i++) {
byTime[i] = ((long) logs[i][1] << BITS) | logs[i][0];
}
Arrays.sort(byTime);
long[] byQuery = new long[k];
for (int i = 0; i < k; i++) {
byQuery[i] = ((long) queries[i] << BITS) | i;
}
Arrays.sort(byQuery);
int[] count = new int[n + 1]; // server ids are 1-based
int active = 0, left = 0, right = 0;
int[] answer = new int[k];
// Answer queries in increasing order so the window only moves right.
for (long packed : byQuery) {
long q = packed >> BITS;
int index = (int) (packed & MASK);
while (right < m && (byTime[right] >> BITS) <= q) {
int server = (int) (byTime[right] & MASK);
if (count[server]++ == 0) {
active++;
}
right++;
}
while (left < right && (byTime[left] >> BITS) < q - x) {
int server = (int) (byTime[left] & MASK);
if (--count[server] == 0) {
active--;
}
left++;
}
answer[index] = n - active;
}
return answer;
}
}