1782. Count Pairs Of Nodes

Explanation

To solve this problem, we need to calculate the incident(a, b) value for all pairs of nodes a and b, and then count the number of pairs that satisfy the given conditions for each query.

Algorithmic Idea

Create a map to store the count of incident edges for each node.
For each pair of nodes a and b, calculate the incident(a, b) value by summing the incident edges of nodes a and b while considering any duplicate edges.
Count the pairs that satisfy the conditions and store the result for each query.

Time Complexity

Calculating incident edges for all pairs: O(edges)
Counting pairs for each query: O(queries) Overall time complexity: O(edges + queries)

Space Complexity

Space required for incident edges map: O(edges)
Space required for storing results: O(queries) Overall space complexity: O(edges + queries)

View Leetcode Problem

class Solution {
    public int[] countPairs(int n, int[][] edges, int[] queries) {
        int[] incident = new int[n + 1];
        Map<Integer, Integer> edgeCount = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            incident[u]++;
            incident[v]++;
            int key = Math.min(u, v) * (n + 1) + Math.max(u, v);
            edgeCount.put(key, edgeCount.getOrDefault(key, 0) + 1);
        }

        int[] counts = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            counts[incident[i]]++;
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int query = queries[i];
            int count = 0;
            for (int j = 1; j <= n; j++) {
                if (incident[j] > query) {
                    count += counts[Math.min(2 * n, incident[j] + query)] - counts[incident[j] + 1];
                }
            }
            for (int key : edgeCount.keySet()) {
                int u = key / (n + 1);
                int v = key % (n + 1);
                if (incident[u] + incident[v] > query && incident[u] + incident[v] - edgeCount.get(key) <= query) {
                    count--;
                }
            }
            res[i] = count / 2;
        }

        return res;
    }
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.