Formatted question description: https://leetcode.ca/all/1782.html
1782. Count Pairs Of Nodes
Level
Hard
Description
You are given an undirected graph represented by an integer n
, which is the number of nodes, and edges
, where edges[i] = [u_i, v_i]
which indicates that there is an undirected edge between u_i
and v_i
. You are also given an integer array queries
.
The answer to the jth
query is the number of pairs of nodes (a, b)
that satisfy the following conditions:
a < b
cnt
is strictly greater thanqueries[j]
, wherecnt
is the number of edges incident toa
orb
.
Return an array answers
such that answers.length == queries.length
and answers[j]
is the answer of the jth
query.
Note that there can be repeated edges.
Example 1:
Input: n = 4, edges = [[1,2],[2,4],[1,3],[2,3],[2,1]], queries = [2,3]
Output: [6,5]
Explanation: The number of edges incident to at least one of each pair is shown above.
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]
Constraints:
2 <= n <= 2 * 10^4
1 <= edges.length <= 10^5
1 <= u_i, v_i <= n
u_i != v_i
1 <= queries.length <= 20
0 <= queries[j] < edges.length
Solution
First, calculate the degrees of each node and the counts of each edge. Next, use another array arr
to store the degrees and sort arr
. Then, for each query, use two pointers to calculate the number of pairs of nodes that satisfy the conditions. Finally, return the query result.

class Solution { public int[] countPairs(int n, int[][] edges, int[] queries) { final int FACTOR = 100000; int[] degrees = new int[n + 1]; int[] arr = new int[n + 1]; int length = queries.length; int[] pairs = new int[length]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int[] edge : edges) { int u = Math.min(edge[0], edge[1]); int v = Math.max(edge[0], edge[1]); degrees[u]++; degrees[v]++; int key = u * FACTOR + v; map.put(key, map.getOrDefault(key, 0) + 1); } for (int i = 1; i <= n; i++) arr[i] = degrees[i]; Arrays.sort(arr); for (int i = 0; i < length; i++) { int low = 1, high = n; while (low < high) { while (low < high && arr[low] + arr[high] <= queries[i]) low++; if (low < high) pairs[i] += high  low; high; } if (pairs[i] != 0) { Set<Integer> visited = new HashSet<Integer>(); for (int[] edge : edges) { int u = Math.min(edge[0], edge[1]); int v = Math.max(edge[0], edge[1]); int key = u * FACTOR + v; if (visited.add(key)) { int pair = degrees[u] + degrees[v]  map.get(key); if (degrees[u] + degrees[v] > queries[i] && pair <= queries[i]) pairs[i]; } } } } return pairs; } }

Todo

print("Todo!")