Count Zero Request Servers

classic intervals question w/ a sliding window solution!

intuitively, because there are a lot of repeat traversals that would occur if we relied on the brute-force strategy of iterating through everything, i am incentivised to pre-process the logs and queries array such that we only require one pass.

in our case, i realised that by sorting both logs and queries in chronological order, we can simply run a sliding window such that for a query q, the window simply holds the logs with times from q - x to q. this means each log will only enter and leave once, so the sweep is a single pass.

the tricky part is that one server can show up in many logs. to combat this, we have:

• active_count to track how many requests each server has inside the window
• active tracks how many servers at least once, so the answer is n - active

finally, since each answer has to refer back to each query's original spot, we sort the indices of queries rather than queries itself to preserve its ordering.

code link to code#

class Solution {
public:
    vector<int> countServers(int n, vector<vector<int>>& logs, int x, vector<int>& queries) {
        sort(logs.begin(), logs.end(),
            [](const auto& a, const auto& b) { return a[1] < b[1]; });
        
        int active{};
        vector<int> active_count(n+1, 0);

        vector<int> indices(queries.size());
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(),
        [&](const auto i, const auto j) { return queries[i] < queries[j]; });

        vector<int> answer(queries.size());
        
        int left = 0, right = 0;
        for (int query_idx : indices) {
            int query = queries[query_idx];
            while (right < logs.size() && logs[right][1] <= query) {
                int id = logs[right++][0];
                if (active_count[id]++ == 0) {
                    ++active;
                }
            }
            while (left < right && logs[left][1] < query - x) {
                int id = logs[left++][0];
                if (--active_count[id] == 0) {
                    --active;
                }
            }
            answer[query_idx] = n - active;
        }

        return answer;
    }
};

complexity link to complexity#

• Time: O(n + k log(k) + m log(m)), where n denotes the number of servers, k denotes the number of logs and m denotes the number of queries
• Space: O(n + m + log(k) + log(m))

learning link to learning#

the sort function inside of cpp uses introspective sort, which is a hybrid between three sorting algorithms:

• by default, it uses quicksort
• however, when the recursion depth passes a threshold, to protect it from quicksort's worst case complexity of O(n^2), it switches to heapsort which has a worst case complexity of O(n log(n))
• then, when sub-partitions become small enough, it swaps to insertion sort because it has lower overhead and uses CPU caching very effectively

even though the sorting is in-place, the space complexity is still O(log(n)) from the function calls from the divide-and-conquer strategy.

time taken link to time taken#

• 11 minutes and 52 seconds