Problem Description

The "Count Pairs Of Nodes" problem asks you to count the number of unique pairs of nodes in an undirected graph that satisfy a particular condition. Given:

• An integer n representing the number of nodes, labeled from 1 to n.
• A list of edges, where each edge is a pair [u, v] indicating an undirected connection between nodes u and v.
• A list queries, where for each queries[i] you must count the number of pairs (a, b) such that a < b and the total number of edges incident to either a or b (counting shared edges only once) is strictly greater than queries[i].

Key constraints:

• Each pair (a, b) is counted only once (order doesn't matter, and a < b).
• Do not reuse edges or nodes in multiple pairs.
• There is only one valid way to count each pair for a given query.

Thought Process

To solve this problem, we first need to understand the graph representation and how to efficiently count pairs. The brute-force approach would be to check every possible pair of nodes and count their combined degree (number of edges attached to either node), then see if it exceeds the query value. However, this would be too slow for large graphs.

The challenge is that some edges may connect the same pair of nodes multiple times (multi-edges), and we should only count each edge once per pair. We also need to efficiently process multiple queries.

The optimization comes from realizing that:

• The degree of each node can be precomputed.
• For each pair, the total unique edge count is deg[a] + deg[b] - shared[a][b], where shared[a][b] is the number of edges directly between a and b.
• We can sort the degree array and use a two-pointer approach to count pairs efficiently for each query.
• Finally, we must adjust counts for pairs that are "over-counted" due to shared edges.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Count Degrees:
   • For each node, count how many edges are attached to it. Store this in an array deg.
2. Count Shared Edges:
   • For each pair of nodes (a, b), count how many direct edges exist between them. Store this in a dictionary shared[(a,b)].
3. Sort Degrees:
   • Sort the degree array. This allows us to use a two-pointer approach to efficiently count pairs whose degree sum exceeds the query value.
4. Two-pointer Counting:
   • For each query, use two pointers (left and right) to count the number of pairs (a, b) such that deg[a] + deg[b] > queries[i].
5. Adjust for Shared Edges:
   • For each directly connected pair, check if their combined degree sum exceeds the query only because of double-counting the shared edge. If so, subtract those cases from the count.
6. Repeat for Each Query:
   • Process all queries and collect the results.

This approach leverages sorting and precomputation to avoid redundant calculations, making it efficient even for large graphs.

Example Walkthrough

Suppose n = 4, edges = [[1,2],[2,3],[1,3],[2,4]], and queries = [2,3].

• Step 1: Count Degrees
  • Node 1: degree 2 (edges to 2 and 3)
  • Node 2: degree 3 (edges to 1, 3, 4)
  • Node 3: degree 2 (edges to 1 and 2)
  • Node 4: degree 1 (edge to 2)
• Step 2: Count Shared Edges
  • (1,2): 1 edge
  • (2,3): 1 edge
  • (1,3): 1 edge
  • (2,4): 1 edge
• Step 3: Sort Degrees
  • Degrees: [1,2,2,3]
• Step 4: For Query = 2
  • Find pairs where deg[a] + deg[b] > 2.
  • By two-pointer: (3,2),(3,2),(3,1),(2,2),(2,1),(2,1) → counting unique pairs: (2,3),(1,2),(1,3),(2,4),(3,4)
  • After adjusting for shared edges, we get the correct count.
• Step 5: For Query = 3
  • Find pairs where deg[a] + deg[b] > 3.
  • By two-pointer: (3,2),(3,2),(3,1) → (2,3),(1,3),(1,2)
  • Adjust for shared edges as above.

This step-by-step process ensures we count only the valid pairs for each query.

Time and Space Complexity

Brute-force Approach:

• Time: O(n²) for each query, since we check every pair.
• Space: O(n²) if we store shared edge counts for every pair.

• Time: O(n log n + m), where n is the number of nodes and m is the number of edges. Sorting degrees is O(n log n), and the two-pointer method is O(n) per query.
• Space: O(n + m), for degrees and shared edge counts.

The optimized approach is much more scalable for large graphs and multiple queries.

Summary

To solve the "Count Pairs Of Nodes" problem efficiently, we:

• Precompute node degrees and shared edge counts.
• Sort degrees for fast two-pointer counting.
• Adjust for over-counted shared edges.
• Process each query efficiently using these precomputations.

Code Implementation

from collections import defaultdict

class Solution:
    def countPairs(self, n, edges, queries):
        deg = [0] * (n + 1)
        shared = defaultdict(int)
        for u, v in edges:
            deg[u] += 1
            deg[v] += 1
            a, b = min(u, v), max(u, v)
            shared[(a, b)] += 1

        sorted_deg = sorted(deg[1:])
        res = []
        for q in queries:
            ans = 0
            l, r = 0, n - 1
            while l < r:
                if sorted_deg[l] + sorted_deg[r] > q:
                    ans += r - l
                    r -= 1
                else:
                    l += 1
            # Adjust for shared edges
            for (a, b), cnt in shared.items():
                if deg[a] + deg[b] > q and deg[a] + deg[b] - cnt <= q:
                    ans -= 1
            res.append(ans)
        return res
      

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<int> deg(n + 1, 0);
        unordered_map<long long, int> shared;
        for (auto& e : edges) {
            int u = e[0], v = e[1];
            deg[u]++;
            deg[v]++;
            int a = min(u, v), b = max(u, v);
            long long key = ((long long)a << 32) | b;
            shared[key]++;
        }
        vector<int> sorted_deg(deg.begin() + 1, deg.end());
        sort(sorted_deg.begin(), sorted_deg.end());
        vector<int> res;
        for (int q : queries) {
            int ans = 0, l = 0, r = n - 1;
            while (l < r) {
                if (sorted_deg[l] + sorted_deg[r] > q) {
                    ans += r - l;
                    r--;
                } else {
                    l++;
                }
            }
            for (auto& it : shared) {
                int a = (int)(it.first >> 32), b = (int)(it.first & 0xFFFFFFFF);
                int cnt = it.second;
                if (deg[a] + deg[b] > q && deg[a] + deg[b] - cnt <= q)
                    ans--;
            }
            res.push_back(ans);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        int[] deg = new int[n + 1];
        Map<Long, Integer> shared = new HashMap<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            deg[u]++;
            deg[v]++;
            int a = Math.min(u, v), b = Math.max(u, v);
            long key = ((long)a << 32) | b;
            shared.put(key, shared.getOrDefault(key, 0) + 1);
        }
        int[] sorted_deg = Arrays.copyOfRange(deg, 1, n + 1);
        Arrays.sort(sorted_deg);
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int q = queries[i], ans = 0, l = 0, r = n - 1;
            while (l < r) {
                if (sorted_deg[l] + sorted_deg[r] > q) {
                    ans += r - l;
                    r--;
                } else {
                    l++;
                }
            }
            for (Map.Entry<Long, Integer> entry : shared.entrySet()) {
                int a = (int)(entry.getKey() >> 32), b = (int)(entry.getKey() & 0xFFFFFFFFL);
                int cnt = entry.getValue();
                if (deg[a] + deg[b] > q && deg[a] + deg[b] - cnt <= q)
                    ans--;
            }
            res[i] = ans;
        }
        return res;
    }
}
      

var countPairs = function(n, edges, queries) {
    const deg = Array(n + 1).fill(0);
    const shared = new Map();
    for (const [u, v] of edges) {
        deg[u]++;
        deg[v]++;
        const a = Math.min(u, v), b = Math.max(u, v);
        const key = a + ',' + b;
        shared.set(key, (shared.get(key) || 0) + 1);
    }
    const sorted_deg = deg.slice(1).sort((a, b) => a - b);
    const res = [];
    for (const q of queries) {
        let ans = 0, l = 0, r = n - 1;
        while (l < r) {
            if (sorted_deg[l] + sorted_deg[r] > q) {
                ans += r - l;
                r--;
            } else {
                l++;
            }
        }
        for (const [key, cnt] of shared.entries()) {
            const [a, b] = key.split(',').map(Number);
            if (deg[a] + deg[b] > q && deg[a] + deg[b] - cnt <= q)
                ans--;
        }
        res.push(ans);
    }
    return res;
};