2747.Count_Zero_Request_Servers(Medium).md

2747. Count Zero Request Servers (Medium)

Date and Time: Jun 5, 2025

Link: https://leetcode.com/problems/count-zero-request-servers

Walk-through:

1. Sort queries in increasing order and logs based on its receiving time. Because the question requires us to return the number in order, so when we sort queries, we need to keep its index, and update ans[] by each query's index.

2. Process each query by using sliding window approach. We can find each query's time interval by [query-x, query], each time we update l ptr if logs[l][1] < (query-x), but we first need to check if increment l will remove existed server in hashmap, if so, we update hashmap. After we have a fix l ptr, we find r ptr by max(r, l), if l is larger, which means we have deleted all the previous servers for current query (they are out of range), and we start incrementing r ptr until logs[r][1] > query.

Python:

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        # Q: Return # servers didn't receive requests during time interval
        # S: 1. Sort queries and logs based on receiving time
        # 2. Use slidng window to save all servers within current query
        # TC: O(nlogn + mlogm), n=len(queries), m=len(logs), SC: O(i), total servers

        queries = sorted((q, i) for i, q in enumerate(queries))
        logs.sort(key=lambda x: x[1])
        ans = [0] * len(queries)
        l, r = 0, 0
        hashmap = collections.defaultdict(int)      # {server: cnt}
        for query, i in queries:
            interval = [query-x, query]
            # Find left bound
            while l <= len(logs)-1 and logs[l][1] < interval[0]:
                # Check to remove previous servers
                if logs[l][0] in hashmap:
                    hashmap[logs[l][0]] -= 1
                    if hashmap[logs[l][0]] == 0:
                        del hashmap[logs[l][0]]
                l += 1
            r = max(r, l)
            # Update r ptr to add server within the right bound
            while r <= len(logs)-1 and logs[r][1] <= interval[1]:
                hashmap[logs[r][0]] += 1
                r += 1
            # Count # servers didn't receive requests
            ans[i] = n - len(hashmap)
        return ans

Time Complexity: $O(nlog(n) + mlog(m))$
Space Complexity: $O(m)$