LeetCode 1782: Count Pairs Of Nodes Solution

Master LeetCode problem 1782 (Count Pairs Of Nodes), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1782. Count Pairs Of Nodes

Hard

Array Two Pointers Binary Search Graph Sorting

Problem Explanation

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)

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1782 (Count Pairs Of Nodes)?

This page provides optimized solutions for LeetCode problem 1782 (Count Pairs Of Nodes) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1782 (Count Pairs Of Nodes)?

The time complexity for LeetCode 1782 (Count Pairs Of Nodes) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1782 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1782 in Java, C++, or Python.

Back to LeetCode Solutions