2747. Count Zero Request Servers

MediumArrayHash TableSortingSliding Window

Problem Description

In this LeetCode problem, we are given the following inputs:

An integer n, which is the total number of servers.
A 2D integer array logs, where each element logs[i] represents an event with two values:
- server_id: which is the ID of the server (0-indexed) that received a request.
- time: the time at which the request was received.
An integer x, which defines the duration of a time interval.
A 0-indexed integer array queries, with each entry representing a point in time.

We are required to find out the number of servers that did not receive any requests during a specific time interval. For each query time queries[i], we want to know how many servers were idle in the time interval from queries[i] - x to queries[i], inclusive.

Our goal is to return an integer array of the same length as queries where the i-th element is the count of servers that were idle during the time interval corresponding to queries[i].

Intuition

To solve this problem, we need to process the time intervals defined by the queries and identify servers that did not receive any requests within these intervals. The solution proposed here involves several key steps:

Use a Counter to keep track of how many requests each server has received in the current time frame. This allows us to determine if a server is idle or not.
Sort the logs by time, allowing us to process events in chronological order and update the counter appropriately.
Sort the queries and use the zip function combined with count() to pair each query with its index, allowing us to retain the original order after processing.
Use two pointers (j and k) to iterate over the logs:
- Pointer k advances through the logs to include all events that fall within the time interval up to the current query time.
- Pointer j advances through the logs to exclude events that are no longer within the current query time interval.
For each query, calculate the number of idle servers by subtracting the number of unique active servers (i.e., those with non-zero request counts in the counter) from the total number of servers, n.
Populate the answer ans array, where each element corresponds to the calculated number of idle servers for that query.

The overall time complexity of the solution is driven by the sorting of logs and queries, and the iteration over them, all of which contribute to an efficient solution.

Learn more about Sorting and Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Solution Approach

The solution provided is written in Python and applies an effective approach for solving the problem using time-series analysis, sorting, and sliding window techniques combined with a hashmap to track the activity of servers. Below is the step-by-step implementation guide:

Sorting Logs by Time: The logs list is first sorted according to the time dimension (x[1]) to process the requests in chronological order.
Initialization: A Counter object cnt is used as a hashmap to keep track of the number of requests each server is currently handling in the time window. An answer list ans is initiated with zeros, each corresponding to the number of idle servers for a particular query.
Sorting Queries: The queries list along with their respective indices is sorted. This allows iteration over time-ordered queries while keeping track of their original position in the queries array.
Iterative Processing with Two Pointers: Two pointers j and k are introduced:
- k moves forward to include requests up to the current query time (r).
- j moves forward to remove requests that are before the start of the current time window (r - x).
These pointers help in creating a sliding window of requests which are currently active/inactive.
Counting Requests and Servers:
- With pointer k, each time a new request is processed (i.e., within the time frame), the corresponding server's count in cnt is increased.
- With pointer j, each time an old request is no longer within the sliding window, the corresponding server's count in cnt is decreased. If the count drops to zero, the server ID is removed from cnt.
Calculating Idle Servers: For each query, the number of servers that did not receive any requests in the specified time frame is calculated by subtracting the number of unique server IDs present in the cnt (active servers) from the total number of servers n. This result is placed into the correct position in the ans array to correspond with the original query order.
```
1ans[i] = n - len(cnt)
```
Return Final Answer: After processing all queries, the ans list contains the count of idle servers for each query time, and this list is returned as the final answer.

This approach efficiently processes each query against the sorted logs to build the output while reusing calculations from previous steps to minimize the computational effort and maintaining an up-to-date representation of server activity over time.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Given:

n = 3 (We have 3 servers in total)
logs = [[0, 1], [1, 2], [2, 3], [1, 4]] (List of event logs)
x = 1 (Duration of time interval)
queries = [2, 4] (Times at which we want to count idle servers)

Process:

Sorting Logs by Time:
Sort logs based on the time they were captured. The logs are already sorted in this example: [[0, 1], [1, 2], [2, 3], [1, 4]].
Initialization:
We start with a Counter called cnt and an answer list ans with zeros:
- cnt = Counter()
- ans = [0, 0] (Since there are two queries)
Sorting Queries:
Sort queries alongside their indices: [(2, 0), (4, 1)] (Query times with original indices).
Iterative Processing with Two Pointers (j and k):
Initialize j = k = 0. We will not detail pointer increments here for brevity.
Counting Requests and Servers:
At query = 2, the events up to time 2 are [0, 1], [1, 2]. We process these requests and update the counter cnt.
After processing, cnt = Counter({0: 1, 1: 1}).
Server 2 has not yet received any requests by time 2.
Calculating Idle Servers for first query:
We find that 1 server (server_id = 2) did not receive any requests in the time frame [2 - 1, 2] (query time minus x, to query time inclusive).
Thus, ans[0] = n - len(cnt) = 3 - 2 = 1.
Moving to the second query at time 4:
Now pointer k should have advanced to include the log [1, 4], and cnt is updated.
No logs are removed since the earlier logs are still within the window [4 - 1, 4], so cnt remains the same.
cnt = Counter({0: 1, 1: 2, 2: 1}) (All servers have received requests between times 3 and 4).
Calculating Idle Servers for second query:
Since all servers are now active, ans[1] = n - len(cnt) = 3 - 3 = 0.

Results:

The answer list ans after processing the queries is [1, 0]. This indicates that there was 1 idle server during the first query time and no idle servers during the second query time.

Final Answer:

The final output returned is [1, 0], representing the count of idle servers at each queried time.

Solution Implementation

1from collections import Counter
2from itertools import count
3
4class Solution:
5    def countServers(self, server_count: int, logs: List[List[int]], time_window: int, queries: List[int]) -> List[int]:
6        """
7        Count the number of offline servers at each query time.
8
9        :param server_count: Number of total servers.
10        :param logs: List of server logs, each containing server id and log time.
11        :param time_window: Time window for considering logs.
12        :param queries: List of times to query the number of offline servers.
13        :return: List of counts of offline servers for each query time.
14        """
15        server_activity_counter = Counter()
16        logs.sort(key=lambda log: log[1])
17        answer = [0] * len(queries)
18        log_index = time_index = 0
19
20        # Sort the queries while keeping track of original indices using itertools.count
21        for query_time, original_index in sorted(zip(queries, count())):
22            # Calculate the lower time limit for the current window
23            lower_time_limit = query_time - time_window
24
25            # Add server logs that are within the current query time window
26            while log_index < len(logs) and logs[log_index][1] <= query_time:
27                server_activity_counter[logs[log_index][0]] += 1
28                log_index += 1
29
30            # Remove server logs that are outside the current time window
31            while time_index < len(logs) and logs[time_index][1] < lower_time_limit:
32                server_activity_counter[logs[time_index][0]] -= 1
33                if server_activity_counter[logs[time_index][0]] == 0:
34                    # If the count for a server becomes 0, remove it from the counter
35                    del server_activity_counter[logs[time_index][0]]
36                time_index += 1
37
38            # The number of offline servers is the total server count minus the number of unique active servers
39            answer[original_index] = server_count - len(server_activity_counter)
40      
41        return answer
42

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4
5class Solution {
6    // Method to count the number of servers that are not busy during query times
7    public int[] countServers(int totalServers, int[][] logs, int timeFrame, int[] queries) {
8        // Sort the logs based on the timestamp
9        Arrays.sort(logs, (a, b) -> a[1] - b[1]);
10
11        // Number of queries
12        int numQueries = queries.length;
13        // Array to hold query and index as pair
14        int[][] sortedQueries = new int[numQueries][0];
15        // Populate with query and index
16        for (int i = 0; i < numQueries; ++i) {
17            sortedQueries[i] = new int[] {queries[i], i};
18        }
19        // Sort the queries based on query time
20        Arrays.sort(sortedQueries, (a, b) -> a[0] - b[0]);
21
22        // Use a Map to keep track of the number of busy servers
23        Map<Integer, Integer> busyServersCount = new HashMap<>();
24        // Array to hold the answer for each query
25        int[] answers = new int[numQueries];
26
27        // Indexes for processing logs
28        int startIndex = 0, endIndex = 0;
29        // Loop over each sorted query
30        for (var query : sortedQueries) {
31            int queryTime = query[0], originalIndex = query[1];
32            int lowerBoundTime = queryTime - timeFrame;
33            // Increment the server usage count for logs within the time frame
34            while (endIndex < logs.length && logs[endIndex][1] <= queryTime) {
35                busyServersCount.merge(logs[endIndex++][0], 1, Integer::sum);
36            }
37            // Decrement the server usage count for logs before the time frame
38            while (startIndex < logs.length && logs[startIndex][1] < lowerBoundTime) {
39                int serverId = logs[startIndex][0];
40                int updatedCount = busyServersCount.merge(serverId, -1, Integer::sum);
41                // Remove from the map if no server is busy
42                if (updatedCount == 0) {
43                    busyServersCount.remove(serverId);
44                }
45                startIndex++;
46            }
47            // Calculate how many servers are not busy
48            answers[originalIndex] = totalServers - busyServersCount.size();
49        }
50        // Return the array of answers for each query
51        return answers;
52    }
53}
54

1#include <vector>
2#include <algorithm>
3#include <unordered_map>
4
5using namespace std;
6
7class Solution {
8public:
9    // This method counts the servers available after filtering out servers that
10    // have sent logs within a certain time frame 'x' for each query time in 'queries'
11    vector<int> countServers(int totalServers, vector<vector<int>>& logs, int timeFrame, vector<int>& queries) {
12        // Sort logs by their time stamp
13        sort(logs.begin(), logs.end(), [](const auto& a, const auto& b) {
14            return a[1] < b[1];
15        });
16
17        int numQueries = queries.size();
18        // Pair queries with their original indices for later reference after sorting
19        vector<pair<int, int>> queryIndexPairs(numQueries);
20        for (int i = 0; i < numQueries; ++i) {
21            queryIndexPairs[i] = {queries[i], i};
22        }
23        // Sort the queryIndexPairs by the query times
24        sort(queryIndexPairs.begin(), queryIndexPairs.end());
25
26        // A map to keep count of logs per server
27        unordered_map<int, int> serverLogCount;
28        // Vector to store the final answer
29        vector<int> answer(numQueries);
30        // Two pointers used to iterate over logs
31        int logStartPointer = 0, logEndPointer = 0;
32        // Iterate over each query
33        for (auto& [queryTime, queryIndex] : queryIndexPairs) {
34            // Calculate the left boundary of the time frame
35            int leftTimeBoundary = queryTime - timeFrame;
36            // Accumulate logs within the time frame right boundary
37            while (logEndPointer < logs.size() && logs[logEndPointer][1] <= queryTime) {
38                ++serverLogCount[logs[logEndPointer++][0]];
39            }
40            // Discard logs that are before the time frame left boundary
41            while (logStartPointer < logs.size() && logs[logStartPointer][1] < leftTimeBoundary) {
42                if (--serverLogCount[logs[logStartPointer][0]] == 0) {
43                    serverLogCount.erase(logs[logStartPointer][0]);
44                }
45                ++logStartPointer;
46            }
47            // Record the count of servers that did NOT send a log during the time frame
48            answer[queryIndex] = totalServers - serverLogCount.size();
49        }
50        return answer;
51    }
52};
53

1function countServers(n: number, logs: number[][], x: number, queries: number[]): number[] {
2    // Sort the server logs by the end time.
3    logs.sort((a, b) => a[1] - b[1]);
4
5    // Number of queries.
6    const numQueries = queries.length;
7
8    // Pair up each query with its index and sort by query time.
9    const queriesWithIndices: number[][] = [];
10    for (let i = 0; i < numQueries; ++i) {
11        queriesWithIndices.push([queries[i], i]);
12    }
13    queriesWithIndices.sort((a, b) => a[0] - b[0]);
14
15    // Map to keep count of active servers.
16    const serverCounts: Map<number, number> = new Map();
17
18    // Array to hold the results.
19    const results: number[] = new Array(numQueries);
20
21    // Index pointers for logs.
22    let logStartIndex = 0;
23    let logEndIndex = 0;
24
25    // Iterate over the sorted queries.
26    for (const [queryTime, index] of queriesWithIndices) {
27        // Calculate the lower time bound for counting servers.
28        const lowerBoundTime = queryTime - x;
29
30        // Add server logs that ended on or before the current query time.
31        while (logEndIndex < logs.length && logs[logEndIndex][1] <= queryTime) {
32            const serverId = logs[logEndIndex][0];
33            serverCounts.set(serverId, (serverCounts.get(serverId) || 0) + 1);
34            ++logEndIndex;
35        }
36
37        // Remove server logs that ended before the lower time bound.
38        while (logStartIndex < logs.length && logs[logStartIndex][1] < lowerBoundTime) {
39            const serverId = logs[logStartIndex][0];
40            serverCounts.set(serverId, (serverCounts.get(serverId) || 0) - 1);
41            if (serverCounts.get(serverId) === 0) {
42                serverCounts.delete(serverId);
43            }
44            ++logStartIndex;
45        }
46
47        // Calculate the number of active servers and store it in the results.
48        results[index] = n - serverCounts.size;
49    }
50    return results;
51}
52

Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

Divide the array into two equal halves by indexDivide the array into two based on whether an element is smaller than an arbitrary valueDivide the array into a stray element and the rest of the arrayQuick sort does not use divide and conquer

I don’t know

Time and Space Complexity

Time Complexity

The overall time complexity of the code can be broken down as follows:

Sorting logs: Sorting the logs list based on timestamp has a time complexity of O(m log m), where m is the length of the logs list.
Iterating over queries: As the queries are sorted together with the count(), the complexity for sorting the zipped list is O(q log q), where q is the number of queries.
Iterating over logs while processing each query: We iterate through the logs twice in a linear fashion, once with k and once with j, but since both k and j only move forward, each log is processed at most twice. This gives us O(m).

Combining these three parts, the dominant terms are the sorting parts, leading to a final time complexity of O(m log m + q log q).

Space Complexity

The space complexity can be broken down as follows:

Storing sorted queries and indexes: This requires O(q) space.
cnt Counter data structure: In the worst case, it will store an entry for every unique server, which is, in the worst case, as large as the length of logs, resulting in O(m) space complexity.
ans list to store the answers: This will take O(q) space.

The combined space complexity, combining the space used by cnt and ans, as well as the temporary space for sorting, is O(m + q).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

[1, 2, 3, 4, 5][1, 3, 6, 10, 15][15, 14, 12, 9, 5][5, 4, 3, 2, 1]

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2747. Count Zero Request Servers

Problem Description

Intuition

Solution Approach

Example Walkthrough

Given:

Process:

Results:

Final Answer:

Solution Implementation

Time and Space Complexity