#1782

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Pairs Of Nodes

Given a graph with nodes and edges, count pairs of nodes where the degree sum exceeds a given threshold for each query.

array hash table two pointers binary search graph

Problem Statement

You are given an undirected graph with n nodes and a list of edges. Each edge connects two nodes. For each query, you need to determine how many pairs of nodes (a, b) have a sum of their degrees greater than a threshold. The degree of a node is defined by the number of edges incident to that node, and an incident(a, b) is the count of edges connected to either a or b.

The challenge is to efficiently calculate the number of valid pairs for multiple queries. The solution involves iterating through node pairs while leveraging hash lookups and degree calculations to determine the result for each query.

Examples

Example 1

Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]

Output: [6,5]

The calculations for incident(a, b) are shown in the table above. The answers for each of the queries are as follows:

answers[0] = 6. All the pairs have an incident(a, b) value greater than 2.
answers[1] = 5. All the pairs except (3, 4) have an incident(a, b) value greater than 3.

Example 2

Input: n = 5, edges = [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], queries = [1,2,3,4,5]

Output: [10,10,9,8,6]

Example details omitted.

Constraints

2 <= n <= 2 * 104
1 <= edges.length <= 105
1 <= ui, vi <= n
ui != vi
1 <= queries.length <= 20
0 <= queries[j] < edges.length

Solution Approach

Precompute Degrees

First, compute the degree for each node in the graph. This step ensures that you can quickly access the degree of any node during later calculations.

Hash Table for Pair Counting

Use a hash table to store counts of pairs for each degree sum. This allows quick lookups during the query processing step to count valid node pairs efficiently.

Query Processing

For each query, iterate over node pairs and calculate the sum of their degrees. Compare it with the threshold and return the count of pairs that satisfy the condition.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is influenced by the number of queries and the number of node pairs considered for each query. Using precomputed degrees and hash lookups helps reduce unnecessary recalculations, but the time complexity will still depend on the graph structure and query size.

What Interviewers Usually Probe

The candidate efficiently uses hash tables to avoid recalculating pair degrees multiple times.
The solution scales well to larger graphs by leveraging precomputation and optimized queries.
The candidate understands how to handle edge cases, such as nodes with no edges or densely connected nodes.

Common Pitfalls or Variants

Common pitfalls

Not handling graphs with nodes that have no edges, leading to incorrect degree calculations.
Using brute force to calculate pairs for each query, which may lead to performance issues for large graphs.
Misunderstanding how to efficiently use hash tables, which could result in unnecessary recomputation.

Follow-up variants

The problem can be modified by changing the threshold in each query, making it more dynamic.
You could add a variation where the graph is directed, affecting how incident pairs are calculated.
Another variant might involve returning the top N node pairs based on the degree sum for each query.

FAQ

What is the main approach for solving 'Count Pairs Of Nodes'?

The main approach is to precompute node degrees, use hash tables for counting pairs, and then efficiently process queries based on these precomputed values.

How can I optimize the solution for large graphs in 'Count Pairs Of Nodes'?

Optimization is achieved by precomputing node degrees and using hash lookups to avoid recalculating degree sums for each query, which ensures the solution scales well.

What common mistakes should I avoid in the 'Count Pairs Of Nodes' problem?

Avoid brute force pair counting and ensure that your solution handles edge cases, such as nodes with no edges or high-density connections.

How does the graph structure affect the solution for 'Count Pairs Of Nodes'?

The graph's structure impacts the number of node pairs considered and the degree calculations. Efficient handling of dense graphs and sparse graphs is crucial for optimal performance.

What are some variations of the 'Count Pairs Of Nodes' problem?

Variants include changing the threshold in queries, handling directed graphs, or returning the top N node pairs based on degree sums.

terminal

Solution

Solution 1: Hash Table + Sorting + Binary Search

From the problem, we know that the number of edges connected to the point pair $(a, b)$ is equal to the "number of edges connected to $a$" plus the "number of edges connected to $b$", minus the number of edges connected to both $a$ and $b$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countPairs(
        self, n: int, edges: List[List[int]], queries: List[int]
    ) -> List[int]:
        cnt = [0] * n
        g = defaultdict(int)
        for a, b in edges:
            a, b = a - 1, b - 1
            a, b = min(a, b), max(a, b)
            cnt[a] += 1
            cnt[b] += 1
            g[(a, b)] += 1

        s = sorted(cnt)
        ans = [0] * len(queries)
        for i, t in enumerate(queries):
            for j, x in enumerate(s):
                k = bisect_right(s, t - x, lo=j + 1)
                ans[i] += n - k
            for (a, b), v in g.items():
                if cnt[a] + cnt[b] > t and cnt[a] + cnt[b] - v <= t:
                    ans[i] -= 1
        return ans

Continue Practicing

#3186 maximum total damage with spell casting #1346 check if n and its double exist #923 3sum with multiplicity