Editorial: LeetCode 1782 Count Pairs of Nodes
https://leetcode.com/problems/count-pairs-of-nodes/ from Amazon
Thinking process:
Another hard problem. To check all pairs, we need a N^2 solution, which is too slow as both the edge length and n are too large.
To count the number of edges incident to a pair (a, b), we just need to add the degree of a and degree of b together and subtract the number of edge(a, b).
With this, we can go through all pairs and use the formula to get the number of edges incident to a pair. However, this is too slow because it’s a N^2 solution.
Look into this problem carefully, we don’t need to check each pairs. We just need to know the “number” of the pairs. To calculate the number of pairs which satisfies the constraint (deg(a)+deg(b) > q), we can use a NlogN solution.
But deg(a) + deg(b) is not the number of edges incident to pair (a, b). We need to subtract the shared number of edges to get the answer. To check this, we need to go through all the edges, which is a O(E) solution.
So the overall time complexity is O(NlogN + E) if we think Q as a constant (at most 20 only).
Here is the code.
1class Solution {
2public:
3 vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
4 vector<int> ans;
5 vector<int> sorted_deg(n+1);
6 vector<int> deg(n+1);
7 vector<unordered_map<int, int>> shared_edge(n+1);
8 for (auto& e : edges) {
9 sorted_deg[e[0]]++;
10 sorted_deg[e[1]]++;
11 deg[e[0]]++;
12 deg[e[1]]++;
13 shared_edge[min(e[0], e[1])][max(e[0], e[1])]++;
14 }
15 sort(sorted_deg.begin(), sorted_deg.end());
16 for (auto q : queries) {
17 ans.push_back(0);
18 int l = 1, r = sorted_deg.size() - 1;
19 for (; l < r;) {
20 if (q < sorted_deg[l] + sorted_deg[r]) {
21 ans.back() += (r - l);
22 r--;
23 } else {
24 l++;
25 }
26 }
27
28 for (int i=1; i<=n; i++) {
29 for (auto [k, v] : shared_edge[i]) {
30 if (q < deg[i] + deg[k] and q >= (deg[i] + deg[k] - v)) {
31 ans.back()--;
32 }
33 }
34 }
35 }
36 return ans;
37 }
38};