#1782

Count Pairs Of Nodes

master · 1670 · lc hard +32 · verified · 42.5% accepted · 345 likes · top 24%

⚑ Converging Pointers (Pair / Triple Sum)

Description

You are given an undirected graph with n nodes and edges (multiple edges allowed), and an integer array queries. incident(a, b) is the number of edges with at least one endpoint in {a, b}. For each query, count pairs (a, b) with a < b and incident(a, b) > queries[j]. Return answers.

Example 1:

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

Output: [6,5]

Explanation: 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]

Code

1

2

3

class Solution:
    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:

class Solution:
    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]: