November 6Medium

Count zero request servers

Array
Hash Table
Sliding Window
Sorting

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

Solution

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        order = { queries[i]: i for i in range(len(queries))}
        queries.sort()
        logs.sort(key = lambda x: x[1])
        l, r = 0, 0
        servers = {}
        ans = [None] * len(queries)

        for q in queries:
            while r < len(logs) and logs[r][1] <= q:
                servers[logs[r][0]] = servers.get(logs[r][0], 0) + 1
                r += 1

            while l < len(logs) and logs[l][1] < q - x:
                servers[logs[l][0]] -= 1
                if not servers[logs[l][0]]:
                    del servers[logs[l][0]]
                l += 1

            ans[order[q]] = n - len(servers)

        return ans