LeetCode 2747 - Count Zero Request Servers

This problem asks us to count servers that did not receive any requests within a certain time window for multiple queries. You are given n servers, each with a unique ID from 1 to n.

leetcodemediumarrayhash-tablesliding-windowsorting

LeetCode Problem 2747

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window, Sorting

Solution

Problem Understanding

This problem asks us to count servers that did not receive any requests within a certain time window for multiple queries. You are given n servers, each with a unique ID from 1 to n. The logs array records requests, where each entry [server_id, time] indicates that server_id received a request at time. For each query q in queries, we are asked to consider the time interval [q - x, q] and count how many servers had no requests in that interval. The expected output is an array of integers, where each integer corresponds to a query.

Inputs include up to 10^5 servers and 10^5 logs and queries, with time values up to 10^6. This indicates that a brute-force scan of all logs for each query is too slow. The problem guarantees that logs and queries are within valid ranges, and servers are numbered from 1 to n.

Important edge cases to consider include queries that occur before any server receives requests, servers that never receive any requests at all, and queries that span multiple requests per server.

Approaches

The brute-force approach would iterate through each query, and for each query, scan all logs to see if a server received a request in the interval [query - x, query]. This would give the correct answer but is inefficient because it requires O(queries * logs) operations, which can reach 10^10-far too slow.

The optimal approach leverages sorting and prefix-like counting using a hash map. First, we group the request times by server. Then, for each query, we check for each server if it had a request in the relevant interval. To make this efficient, we sort the logs by time and use a two-pointer approach to maintain a sliding window of active servers within the interval [query - x, query]. This reduces redundant checks and allows counting servers without requests efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(Q * L) O(1) Scan all logs for each query, slow for large inputs
Optimal O(L log L + Q log Q + L + Q) O(L + Q + N) Sort logs and queries, use two pointers and hashmap to track active servers

Algorithm Walkthrough

  1. Group logs by server: Iterate through logs and store the request times for each server in a dictionary keyed by server_id.
  2. Sort logs and queries: Sort all request times and sort queries in ascending order to facilitate a sliding window.
  3. Initialize data structures: Maintain a counter or hash map to track servers that have requests in the current interval. Also, prepare a result array of length equal to queries.
  4. Process queries with sliding window: Use two pointers on the sorted logs. For a query q, advance the "end" pointer to include logs <= q and advance the "start" pointer to remove logs < q - x. Keep the hash map updated with counts of requests in the current window.
  5. Count zero-request servers: For each query, subtract the number of servers with requests in the interval from n to get the number of zero-request servers.
  6. Return results: Return the result array corresponding to the queries.

Why it works: The sliding window ensures that for each query, we maintain an exact count of servers with requests in the interval [query - x, query] without rescanning all logs. By keeping logs sorted and moving pointers linearly, we avoid redundant checks and guarantee correctness.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countServers(self, n: int, logs: List[List[int]], x: int, queries: List[int]) -> List[int]:
        logs.sort(key=lambda log: log[1])
        sorted_queries = sorted((q, i) for i, q in enumerate(queries))
        result = [0] * len(queries)
        
        count = defaultdict(int)
        start = 0
        end = 0
        L = len(logs)
        
        for q, idx in sorted_queries:
            # Move end pointer to include logs <= q
            while end < L and logs[end][1] <= q:
                count[logs[end][0]] += 1
                end += 1
            # Move start pointer to exclude logs < q - x
            while start < L and logs[start][1] < q - x:
                count[logs[start][0]] -= 1
                if count[logs[start][0]] == 0:
                    del count[logs[start][0]]
                start += 1
            result[idx] = n - len(count)
        
        return result

Explanation: We sort logs by time and pair queries with their original indices. Two pointers (start and end) maintain the sliding window of relevant logs for the current query. The count dictionary tracks how many requests each server has in the window. For each query, the number of zero-request servers is n - len(count).

Go Solution

package main

func countServers(n int, logs [][]int, x int, queries []int) []int {
    type queryIndex struct {
        val int
        idx int
    }
    
    L := len(logs)
    result := make([]int, len(queries))
    sort.Slice(logs, func(i, j int) bool { return logs[i][1] < logs[j][1] })
    
    qWithIndex := make([]queryIndex, len(queries))
    for i, q := range queries {
        qWithIndex[i] = queryIndex{q, i}
    }
    sort.Slice(qWithIndex, func(i, j int) bool { return qWithIndex[i].val < qWithIndex[j].val })
    
    count := make(map[int]int)
    start, end := 0, 0
    
    for _, qi := range qWithIndex {
        q := qi.val
        idx := qi.idx
        for end < L && logs[end][1] <= q {
            count[logs[end][0]]++
            end++
        }
        for start < L && logs[start][1] < q - x {
            count[logs[start][0]]--
            if count[logs[start][0]] == 0 {
                delete(count, logs[start][0])
            }
            start++
        }
        result[idx] = n - len(count)
    }
    
    return result
}

Explanation: The Go solution mirrors the Python logic. We define a struct to keep track of query indices after sorting. We use a map to count servers in the interval and two pointers for the sliding window. We handle deletion of servers from the map when their count drops to zero.

Worked Examples

Example 1

n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]

Sorted logs: [[1,3],[1,5],[2,6]]

Sorted queries: [10,11]

For query 10, interval [5,10]: logs included are [1,5],[2,6]. Servers with requests: {1,2} → zero-request servers = 3 - 2 = 1.

For query 11, interval [6,11]: logs included are [2,6]. Servers with requests: {2} → zero-request servers = 3 - 1 = 2.

Example 2

n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]

Sorted logs: [[2,1],[3,1],[1,2],[2,4]]

Sorted queries: [3,4]

Query 3, interval [1,3]: logs [2,1],[3,1],[1,2]. Servers {1,2,3} → zero-request servers = 0.

Query 4, interval [2,4]: logs [1,2],[2,4]. Servers {1,2} → zero-request servers = 1.

Complexity Analysis

Measure Complexity Explanation
Time O(L log L + Q log Q + L + Q) Sorting logs and queries, then linear scan with two pointers
Space O(L + Q + N) Map for server counts and result array

The sorting dominates the time complexity, and the sliding window ensures we process each log only once.

Test Cases

# Provided examples
assert Solution().countServers(3, [[1,3],[2,6],[1,5]], 5, [10,11]) == [1,2]  # Example 1
assert Solution().countServers(3, [[2,4],[2,1],[1,2],[3,1]], 2, [3,4]) == [0,1]  # Example 2

# Edge cases
assert Solution().countServers(1, [[1,1]], 1, [1]) == [0]  # Single server receives request
assert Solution().countServers(2, [[1,1]], 1, [2]) == [1]  # One server without requests
assert Solution().countServers(