Count Zero Request Servers - Practice Coding Problems

Count Zero Request Servers - 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.

Input & Output

Example 1 — Basic Case

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

› Output: [1,2]

💡 Note: For query 10: window [5,10] contains logs [1,5] and [2,6], so servers {1,2} are active, leaving 1 server with zero requests. For query 11: window [6,11] contains only [2,6], so server {2} is active, leaving 2 servers with zero requests.

Example 2 — No Active Servers

$ Input: n = 2, logs = [[1,1],[2,2]], x = 1, queries = [5]

› Output: [2]

💡 Note: Query 5 with window [4,5] contains no logs, so all 2 servers have zero requests.

Example 3 — All Servers Active

$ Input: n = 3, logs = [[1,1],[2,2],[3,3]], x = 2, queries = [3]

› Output: [0]

💡 Note: Query 3 with window [1,3] contains all logs, so all 3 servers are active, leaving 0 servers with zero requests.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ logs.length ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
logs[i].length == 2
1 ≤ logs[i][0] ≤ n
1 ≤ logs[i][1] ≤ 10⁶
1 ≤ x ≤ 10⁵
x + 1 ≤ queries[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

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

Process

For each query, find active servers in [query-x, query] window

Output

Count servers with zero requests: [1,2]

Key Takeaway

🎯 Key Insight: Sort logs by time to enable efficient range queries for each time window

Asked in

a Amazon 25 G Google 18 M Microsoft 12 f Meta 8

The key insight is to efficiently find servers active in each time window [query-x, query]. The optimal approach sorts both logs by time and queries by value, then uses sliding window technique to process queries efficiently. Time: O(logs×log(logs) + queries×log(queries)), Space: O(logs + queries)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Sorted Queries	O(logs×log(logs) + queries×log(queries) + logs + queries)	O(logs + queries)	Sort both logs and queries, then use sliding window to process queries efficiently
Brute Force	O(queries × logs)	O(n)	For each query, check all logs to count servers with requests in the time window
Sort and Binary Search	O(logs×log(logs) + queries×logs)	O(logs + n)	Sort logs by time, then use binary search to find logs in each query window

Sliding Window with Sorted Queries — Algorithm Steps

Sort logs by time and queries by value (keeping original indices)
Use two pointers to maintain sliding window of active logs
For each query, adjust window and count unique active servers

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Both

Sort logs by time and queries by value

Process Order

Process queries in sorted order for efficiency

Reuse Work

Leverage sorted order to avoid redundant calculations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int value;
    int index;
} QueryInfo;

int compareByTime(const void* a, const void* b) {
    int* logA = *(int**)a;
    int* logB = *(int**)b;
    return logA[1] - logB[1];
}

int compareQueries(const void* a, const void* b) {
    QueryInfo* qA = (QueryInfo*)a;
    QueryInfo* qB = (QueryInfo*)b;
    return qA->value - qB->value;
}

int* solution(int n, int** logs, int logsSize, int x, int* queries, int queriesSize, int* returnSize) {
    // Sort logs by time
    qsort(logs, logsSize, sizeof(int*), compareByTime);
    
    // Create indexed queries and sort by value
    QueryInfo* indexedQueries = (QueryInfo*)malloc(queriesSize * sizeof(QueryInfo));
    for (int i = 0; i < queriesSize; i++) {
        indexedQueries[i].value = queries[i];
        indexedQueries[i].index = i;
    }
    qsort(indexedQueries, queriesSize, sizeof(QueryInfo), compareQueries);
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    
    for (int i = 0; i < queriesSize; i++) {
        int queryVal = indexedQueries[i].value;
        int origIdx = indexedQueries[i].index;
        int startTime = queryVal - x;
        int endTime = queryVal;
        
        int activeServers[1001] = {0};
        int activeCount = 0;
        
        for (int j = 0; j < logsSize; j++) {
            int time = logs[j][1];
            if (time < startTime) continue;
            if (time > endTime) break;
            
            int serverId = logs[j][0];
            if (!activeServers[serverId]) {
                activeServers[serverId] = 1;
                activeCount++;
            }
        }
        
        result[origIdx] = n - activeCount;
    }
    
    free(indexedQueries);
    return result;
}

int main() {
    int n, x, logsSize, queriesSize;
    scanf("%d", &n);
    
    scanf("%d", &logsSize);
    int** logs = (int**)malloc(logsSize * sizeof(int*));
    for (int i = 0; i < logsSize; i++) {
        logs[i] = (int*)malloc(2 * sizeof(int));
        scanf("%d %d", &logs[i][0], &logs[i][1]);
    }
    
    scanf("%d", &x);
    
    scanf("%d", &queriesSize);
    int* queries = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) {
        scanf("%d", &queries[i]);
    }
    
    int returnSize;
    int* result = solution(n, logs, logsSize, x, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(logs×log(logs) + queries×log(queries) + logs + queries)

Sorting both arrays plus single pass through logs and queries

⚡ Linearithmic

Space Complexity

O(logs + queries)

Space for sorted arrays and hash set to track active servers

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Sorted Queries — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler