You are given an undirected graph defined by an integer n, the number of nodes, and a 2D integer array edges, the edges in the graph, where edges[i] = [ui, vi] indicates that there is an undirected edge between ui and
vi. You are also given an integer array queries.
Let incident(a, b) be defined as the number of edges that are connected to either node a or b.
The answer to the jth query is the number of pairs of nodes (a, b)
that satisfy both of the following conditions:
a < b
incident(a, b) > queries[j]
Return an arrayanswerssuch thatanswers.length == queries.lengthandanswers[j]is the answer of thejthquery.
Note that there can be multiple edges between the same two nodes.

Input: n =4, edges =[[1,2],[2,4],[1,3],[2,3],[2,1]], queries =[2,3] Output:[6,5] Explanation: The calculations forincident(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.
The key is to count the number of pairs (a, b) such that the sum of their degrees (number of incident edges) minus the number of shared edges is greater than the query. We use sorting and two pointers to efficiently count such pairs for each query.
classSolution {
funcountPairs(n: Int, edges: Array<IntArray>, queries: IntArray): IntArray {
val deg = IntArray(n+1)
val cnt = mutableMapOf<Pair<Int,Int>, Int>()
for (e in edges) {
val u = minOf(e[0], e[1])
val v = maxOf(e[0], e[1])
deg[u]++; deg[v]++ cnt[u to v] = cnt.getOrDefault(u to v, 0) + 1 }
val sortedDeg = deg.slice(1..n).sorted()
val ans = IntArray(queries.size)
for ((k, q) in queries.withIndex()) {
var res = 0var l = 0; var r = n-1while (l < r) {
if (sortedDeg[l] + sortedDeg[r] > q) {
res += r - l
r-- } else {
l++ }
}
for ((p, c) in cnt) {
val(u, v) = p
if (deg[u] + deg[v] > q && deg[u] + deg[v] - c <= q) res-- }
ans[k] = res
}
return ans
}
}
classSolution:
defcountPairs(self, n: int, edges: list[list[int]], queries: list[int]) -> list[int]:
deg = [0] * (n+1)
cnt = {}
for u, v in edges:
if u > v:
u, v = v, u
deg[u] +=1 deg[v] +=1 cnt[(u, v)] = cnt.get((u, v), 0) +1 sorted_deg = sorted(deg[1:])
ans = []
for q in queries:
res =0 l, r =0, n-1while l < r:
if sorted_deg[l] + sorted_deg[r] > q:
res += r - l
r -=1else:
l +=1for (u, v), c in cnt.items():
if deg[u] + deg[v] > q and deg[u] + deg[v] - c <= q:
res -=1 ans.append(res)
return ans
⏰ Time complexity: O(n log n + m + qn) where n is the number of nodes, m is the number of edges, and q is the number of queries. Sorting and two pointers dominate.
🧺 Space complexity: O(n + m) for degree and edge count storage.