LeetCode Problem 1782

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Two Pointers, Binary Search, Graph Theory, Sorting, Counting

Solution

LeetCode 1782 - Count Pairs Of Nodes

Problem Understanding

We are given an undirected graph with n nodes and a list of edges. Multiple edges between the same pair of nodes are allowed.

For any pair of nodes (a, b), define incident(a, b) as the number of edges connected to either node a or node b.

At first glance, it may seem that this value is simply:

$$degree(a) + degree(b)$$

However, this is not always correct. If there are edges directly connecting a and b, those edges are counted in both degrees. Since incident(a, b) counts edges connected to either node, each shared edge should only be counted once.

If there are c edges between a and b, then:

$$incident(a,b)=degree(a)+degree(b)-c$$

For each query value q, we must count how many pairs (a,b) with a < b satisfy:

$$incident(a,b) > q$$

The constraints are large:

• n ≤ 2 × 10^4
• edges.length ≤ 10^5
• queries.length ≤ 20

A brute force solution that examines all node pairs would require checking roughly:

$$\frac{n(n-1)}{2}$$

pairs, which is about 200 million pairs when n = 20000. This is far too slow.

Several details make the problem tricky:

• Multiple edges can exist between the same nodes.
• Degrees count every edge occurrence.
• Direct connections between a pair cause double-counting.
• We must answer multiple queries efficiently.
• The graph is sparse relative to the number of possible node pairs.

The key challenge is counting pairs with large degree sums without explicitly examining all pairs.

Approaches

Brute Force

The most direct approach computes the degree of every node and the multiplicity of every edge pair.

For each query:

1. Enumerate every pair (a,b).
2. Compute degree[a] + degree[b].
3. Subtract the number of direct edges between them.
4. Check whether the result exceeds the query.

This is correct because it directly implements the definition of incident(a,b).

Unfortunately, there are O(n²) pairs. With n = 20000, this becomes infeasible.

Key Insight

Suppose we temporarily ignore duplicate counting caused by direct edges.

Then the condition becomes:

$$degree(a)+degree(b) > q$$

This is a classic pair-counting problem.

If we sort all node degrees, we can count the number of pairs whose sum exceeds q using the two-pointer technique in O(n) time.

However, some of those counted pairs are invalid.

Consider a pair with:

$$degree(a)+degree(b) > q$$

but

$$degree(a)+degree(b)-c \le q$$

where c is the number of edges directly connecting them.

Such pairs were counted by the degree-sum calculation but should not appear in the final answer.

The correction is possible because the number of distinct node pairs that actually share edges is at most edges.length, which is only 10^5.

Thus:

1. Count all pairs with degree sum exceeding the query.
2. Examine only node pairs that share edges.
3. Subtract those that were incorrectly counted.

This yields an efficient solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(k·n²)	O(n + m)	Check every node pair for every query
Optimal	O(k·(n + m) + n log n)	O(n + m)	Two pointers plus correction using edge multiplicities

Here:

• n = number of nodes
• m = number of edges
• k = number of queries

Algorithm Walkthrough

Step 1: Compute node degrees

Create an array degree.

For every edge (u,v):

• Increment degree[u]
• Increment degree[v]

This gives the total number of incident edges for each node.

Step 2: Record edge multiplicities

Because multiple edges may connect the same pair of nodes, store:

$$count(u,v)$$

for every unordered pair.

Always store the pair in sorted order:

$$(min(u,v), max(u,v))$$

This allows direct lookup later.

Step 3: Sort the degree sequence

Create a sorted copy of all node degrees.

This array will be used for efficient pair counting.

Step 4: Count pairs by degree sum

For a query q, use two pointers.

1. Set left = 0
2. Set right = n - 1

While left < right:

• If

$$sorted[left] + sorted[right] > q$$

then every element between left and right-1 paired with right also exceeds q.

Add:

$$right-left$$

to the answer and decrement right.

Otherwise increment left.

This counts all pairs whose degree sum exceeds q.

Step 5: Remove overcounted pairs

For every node pair (u,v) that has at least one direct edge:

Let:

$$s = degree(u)+degree(v)$$

and let:

$$c = count(u,v)$$

If:

$$s > q$$

but

$$s-c \le q$$

then this pair was counted in Step 4 but should not be counted in the final answer.

Subtract one from the answer.

Step 6: Store the result

After all corrections, store the final count for the current query.

Repeat for every query.

Why it works

The two-pointer phase counts exactly all pairs whose degree sum exceeds the query threshold. For node pairs without direct edges, degree sum equals the incident count, so those pairs are already correct.

For node pairs with direct edges, degree sums overestimate the true incident count by exactly the number of shared edges. The correction phase identifies precisely those pairs whose degree sum exceeds the threshold but whose true incident count does not. Subtracting those pairs removes every false positive and leaves exactly the valid pairs.

Problem Understanding

The problem gives an undirected graph with n nodes and a list of edges, where multiple edges between the same pair of nodes are allowed. Each node has a degree defined by how many edges are incident to it, counting multiplicity.

For any pair of distinct nodes (a, b) with a < b, we define incident(a, b) as the number of edges that are connected to either a or b. Importantly, edges between a and b themselves must only be counted once in this value, even though they contribute to both endpoints’ degrees.

Each query asks: how many pairs (a, b) satisfy incident(a, b) > queries[j].

The output is an array of answers, one per query.

The constraints are large: up to 2 * 10^4 nodes and 10^5 edges, with up to 20 queries. This strongly suggests that per-query O(n log n) or O(n) solutions are acceptable, but anything quadratic over edges or nodes will be too slow.

Edge cases that matter include graphs with many duplicate edges between the same nodes, completely disconnected nodes, and nodes with very high degree skew (star-like structures). Another subtle issue is correctly handling multiple edges between the same two nodes, since they affect both degree sums and corrections.

Approaches

Brute Force Approach

The most direct approach is to compute incident(a, b) for every pair of nodes (a, b) and then answer each query by checking whether it exceeds the threshold.

To compute incident(a, b) naively, we would either scan all edges for each pair or precompute adjacency counts and combine them. Even with adjacency maps, iterating over all O(n^2) pairs dominates the complexity.

Since n can be up to 2 * 10^4, there are about 2 * 10^8 pairs, which is far too large. Even computing a constant-time check per pair would be too slow, and doing this for each query makes it worse.

Key Insight for Optimization

We separate the problem into two parts:

First, ignore the complication of multiple edges between the same pair. If we define deg[a] as the degree of node a, then for any pair (a, b), the naive sum deg[a] + deg[b] counts all incident edges, but it double-counts edges directly between a and b.

If there are cnt(a, b) edges between a and b, then the correct value is:

incident(a, b) = deg[a] + deg[b] - cnt(a, b)

This leads to a natural decomposition:

We first count how many pairs satisfy deg[a] + deg[b] > query. This can be done efficiently using sorting and a two-pointer technique.

However, this overcounts some pairs where the subtraction of cnt(a, b) makes them fall below or equal to the threshold. We fix this by explicitly correcting only the pairs that share edges, using a hash map of edge multiplicities.

So the solution becomes:

1. Count all valid pairs based on degree sums.
2. Subtract invalid pairs caused by shared edges for each query.

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² + m) per query	O(1) or O(m)	Computes every pair directly
Optimal	O(n log n + m log Q)	O(n + m)	Uses sorting + two pointers + correction for duplicate edges

Algorithm Walkthrough

The optimal solution is built in two phases: preprocessing and query answering.

Step 1: Compute degrees and edge multiplicities

We iterate over all edges and compute:

• deg[x]: degree of each node including duplicates
• cnt[(x, y)]: number of edges between x and y

This allows us to later correct overcounted pairs.

Step 2: Sort degrees

We create a sorted array of degrees. This is essential for efficiently counting pairs with a two-pointer technique.

Step 3: Preprocess edge multiplicities

We store each undirected edge in a map with normalized ordering (min(u, v), max(u, v)) to track how many parallel edges exist.

Step 4: Sort queries

We sort queries while keeping their original indices so we can answer them in increasing order efficiently.

Step 5: Count base pairs using two pointers

For each query q, we count the number of pairs (i, j) such that:

deg[i] + deg[j] > q

We do this using two pointers:

We start with l = 0, r = n - 1. If deg[l] + deg[r] > q, then all pairs (l, l+1 ... r) are valid with l, so we add (r - l) and decrement r. Otherwise, we increment l.

This gives us a fast O(n) per query counting method.

Step 6: Correct overcounted pairs

For each edge (u, v) with multiplicity c, we compute:

deg[u] + deg[v]

The base method counts (u, v) as valid if this sum exceeds q, but the true condition is:

deg[u] + deg[v] - c > q

So an error occurs when:

deg[u] + deg[v] > q
and
deg[u] + deg[v] - c <= q

This means:

q ∈ [deg[u] + deg[v] - c, deg[u] + deg[v] - 1]

For each query, we subtract such invalid contributions using binary search over sorted queries.

Why it works

The key invariant is that all pairs are first counted under a relaxed metric (deg[a] + deg[b]), which is monotonic and efficiently queryable. The only deviation from correctness comes from internal edges between pairs, and those are sparse (at most m), allowing targeted corrections. By isolating these corrections, we avoid recomputing pairwise structure entirely.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
        degree = [0] * (n + 1)
        edge_count = defaultdict(int)

        for u, v in edges:
            degree[u] += 1
            degree[v] += 1

            if u > v:
                u, v = v, u

            edge_count[(u, v)] += 1

        sorted_degrees = sorted(degree[1:])

        answers = []

        for q in queries:
            total = 0

            left = 0
            right = n - 1

            while left < right:
                if sorted_degrees[left] + sorted_degrees[right] > q:
                    total += right - left
                    right -= 1
                else:
                    left += 1

            for (u, v), cnt in edge_count.items():
                degree_sum = degree[u] + degree[v]

                if degree_sum > q and degree_sum - cnt <= q:
                    total -= 1

            answers.append(total)

        return answers

Implementation Explanation

The first loop computes both node degrees and the multiplicity of every unordered node pair. The degree array stores how many edge occurrences touch each node. The hash map stores how many parallel edges exist between each pair.

The sorted degree array is built once and reused for every query.

For each query, the two-pointer scan counts all pairs whose degree sum exceeds the threshold. This works because the degree sequence is sorted.

The correction loop then examines only node pairs that actually share edges. If removing the duplicated contribution of shared edges causes the pair to fall below or equal to the threshold, the pair was incorrectly counted and must be removed.

The final answer for each query is appended to the result list. import bisect

class Solution: def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]: deg = [0] * (n + 1) cnt = defaultdict(int)

    for u, v in edges:
        deg[u] += 1
        deg[v] += 1
        if u > v:
            u, v = v, u
        cnt[(u, v)] += 1

    sorted_deg = sorted(deg[1:])
    sorted_queries = sorted((q, i) for i, q in enumerate(queries))
    res = [0] * len(queries)

    m = len(sorted_deg)

    def count_greater(q):
        l, r = 0, m - 1
        ans = 0
        while l < r:
            if sorted_deg[l] + sorted_deg[r] > q:
                ans += (r - l)
                r -= 1
            else:
                l += 1
        return ans

    for q, qi in sorted_queries:
        base = count_greater(q)
        res[qi] = base

    for (u, v), c in cnt.items():
        if u == v:
            continue
        su = deg[u] + deg[v]

        for q, qi in sorted_queries:
            if su > q and su - c <= q:
                res[qi] -= 1

    return res

### Code Explanation

The solution begins by computing degrees and storing edge multiplicities in a hash map. The degree array is then sorted to allow efficient two-pointer counting of valid pairs for each query.

The function `count_greater` computes how many pairs have degree sum greater than a threshold using a linear scan from both ends.

After computing base answers, we iterate over all edges and adjust results for queries where the edge causes overcounting. This ensures correctness in cases where multiple edges reduce the true incident count below the threshold.

## Go Solution

```go
package main

import "sort"

func countPairs(n int, edges [][]int, queries []int) []int {
	degree := make([]int, n+1)

	type Pair struct {
		u int
		v int
	}

	edgeCount := make(map[Pair]int)

	for _, e := range edges {
		u, v := e[0], e[1]

		degree[u]++
		degree[v]++

		if u > v {
			u, v = v, u
		}

		edgeCount[Pair{u, v}]++
	}

	sortedDegrees := make([]int, n)
	for i := 1; i <= n; i++ {
		sortedDegrees[i-1] = degree[i]
	}

	sort.Ints(sortedDegrees)

	ans := make([]int, len(queries))

	for qi, q := range queries {
		total := 0

		left := 0
		right := n - 1

		for left < right {
			if sortedDegrees[left]+sortedDegrees[right] > q {
				total += right - left
				right--
			} else {
				left++
			}
		}

		for p, cnt := range edgeCount {
			degreeSum := degree[p.u] + degree[p.v]

			if degreeSum > q && degreeSum-cnt <= q {
				total--
			}
		}

		ans[qi] = total
	}

	return ans
}

Go-Specific Notes

The Go solution mirrors the Python implementation closely.

A custom Pair struct is used as the key in the hash map because Go maps cannot directly use slices as keys. The degree array uses int, which is sufficient because the largest possible degree is at most 2 × 10^5.

The sorted degree slice is created once and reused for every query. func countPairs(n int, edges [][]int, queries []int) []int { deg := make([]int, n+1) cnt := make(map[[2]int]int)

for _, e := range edges {
	u, v := e[0], e[1]
	deg[u]++
	deg[v]++
	if u > v {
		u, v = v, u
	}
	cnt[[2]int{u, v}]++
}

arr := make([]int, n)
for i := 1; i <= n; i++ {
	arr[i-1] = deg[i]
}

sortInts(arr)

type pair struct {
	q int
	i int
}

sortedQ := make([]pair, len(queries))
for i, q := range queries {
	sortedQ[i] = pair{q, i}
}

sort.Slice(sortedQ, func(i, j int) bool {
	return sortedQ[i].q < sortedQ[j].q
})

res := make([]int, len(queries))

countGreater := func(q int) int {
	l, r := 0, len(arr)-1
	ans := 0
	for l < r {
		if arr[l]+arr[r] > q {
			ans += (r - l)
			r--
		} else {
			l++
		}
	}
	return ans
}

for _, p := range sortedQ {
	res[p.i] = countGreater(p.q)
}

for key, c := range cnt {
	u, v := key[0], key[1]
	if u == v {
		continue
	}
	su := deg[u] + deg[v]

	for _, p := range sortedQ {
		if su > p.q && su-c <= p.q {
			res[p.i]--
		}
	}
}

return res

}

func sortInts(a []int) { for i := 1; i < len(a); i++ { j := i for j > 0 && a[j-1] > a[j] { a[j-1], a[j] = a[j], a[j-1] j-- } } }

### Go-specific Notes

In Go, we explicitly implement sorting for simplicity, though in production one would use `sort.Ints`. We also use a fixed-size array for query pairing to maintain indices. Maps use a tuple key `[2]int` to represent undirected edges.

## Worked Examples

### Example 1

Input:

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

### Degree Computation

| Node | Degree |
| --- | --- |
| 1 | 3 |
| 2 | 4 |
| 3 | 2 |
| 4 | 1 |

Sorted degrees:

| Index | Value |
| --- | --- |
| 0 | 1 |
| 1 | 2 |
| 2 | 3 |
| 3 | 4 |

Edge multiplicities:

| Pair | Count |
| --- | --- |
| (1,2) | 2 |
| (2,4) | 1 |
| (1,3) | 1 |
| (2,3) | 1 |

### Query = 2

Two-pointer counting:

| Left | Right | Sum | Action | Total |
| --- | --- | --- | --- | --- |
| 0 | 3 | 5 | add 3 | 3 |
| 0 | 2 | 4 | add 2 | 5 |
| 0 | 1 | 3 | add 1 | 6 |

Initial count = 6.

Correction phase:

No pair satisfies:

degreeSum > 2 degreeSum - edgeCount <= 2

Final answer:

6

### Query = 3

Two-pointer counting:

| Left | Right | Sum | Action | Total |
| --- | --- | --- | --- | --- |
| 0 | 3 | 5 | add 3 | 3 |
| 0 | 2 | 4 | add 2 | 5 |
| 0 | 1 | 3 | move left | 5 |

Initial count = 5.

Correction phase:

No overcounted pairs exist.

Final answer:

5

Output:

[6,5]

### 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]

Degrees:

| Node | Degree |
| --- | --- |
| 1 | 4 |
| 2 | 2 |
| 3 | 3 |
| 4 | 1 |
| 5 | 6 |

Sorted:

[1,2,3,4,6]

Running the algorithm for each query yields:

[10,10,9,8,6]

which matches the expected output.
For `n = 4`, edges include duplicates between nodes 1 and 2.

First we compute degrees:

Node 1: 3

Node 2: 4

Node 3: 2

Node 4: 1

Sorted degrees: `[1, 2, 3, 4]`

For query `q = 2`, we count pairs with sum greater than 2:

All pairs except possibly smallest ones still qualify, yielding base count 6.

Then we adjust using duplicate edge (1,2), which reduces incident by 2 for that pair, but still keeps it above thresholds in this case.

For `q = 3`, similar reasoning applies but one pair fails after correction, reducing answer by 1.

### Example 2

Degrees are computed from a dense multi-edge graph.

Sorted degrees allow fast computation of base pair counts.

Each query filters progressively more pairs, decreasing results from 10 down to 6.

Edge corrections are applied per duplicate edge, ensuring no pair is incorrectly counted due to shared edges.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n log n + k(n + m)) | Sort once, then process each query with two pointers and corrections |
| Space | O(n + m) | Degree array plus edge multiplicity map |

Here:

- `n` is the number of nodes.
- `m` is the number of edges.
- `k` is the number of queries.

The sorting step costs `O(n log n)`. For each query, the two-pointer scan requires `O(n)` time. The correction phase iterates over all distinct node pairs that share edges, which is at most `O(m)`. Since `k ≤ 20`, the total running time easily fits within the constraints.

## Test Cases

```python
from typing import List

s = Solution()

assert s.countPairs(
    4,
    [[1,2],[2,4],[1,3],[2,3],[2,1]],
    [2,3]
) == [6,5]  # Example 1

assert s.countPairs(
    5,
    [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]],
    [1,2,3,4,5]
) == [10,10,9,8,6]  # Example 2

assert s.countPairs(
    2,
    [[1,2]],
    [0,1]
) == [1,0]  # Smallest graph

assert s.countPairs(
    3,
    [[1,2],[1,2],[1,2]],
    [0,2,3]
) == [3,1,0]  # Multiple parallel edges

assert s.countPairs(
    4,
    [[1,2]],
    [0,1,2]
) == [1,0,0]  # Mostly isolated nodes

assert s.countPairs(
    4,
    [[1,2],[2,3],[3,4]],
    [0]
) == [6]  # Every pair exceeds zero

assert s.countPairs(
    5,
    [[1,2],[1,2],[2,3],[2,3]],
    [3]
) == [3]  # Correction phase required

assert s.countPairs(
    6,
    [[1,2],[1,3],[1,4],[1,5],[1,6]],
    [1,2,3]
) == [9,5,0]  # Star graph

Test Summary

Test	Why
Example 1	Official sample
Example 2	Official sample with multiple edges
Two nodes, one edge	Smallest valid graph
Repeated parallel edges	Verifies multiplicity handling
Mostly isolated nodes	Tests low-degree nodes
Simple path graph	Tests ordinary degree counting
Correction-required graph	Verifies overcount removal logic
Star graph	Tests highly skewed degree distribution

Edge Cases

Multiple Edges Between the Same Pair

This is the most important edge case in the problem. If nodes u and v are connected by several parallel edges, then degree[u] + degree[v] counts those edges twice. A solution that only uses degree sums will overcount some pairs. The implementation stores the multiplicity of every node pair and performs the correction step to handle this exactly.

Large Numbers of Isolated Nodes

Many nodes may have degree zero. After sorting, the degree array can contain long runs of zeros. The two-pointer counting method naturally handles this because pairs involving zero-degree nodes only contribute when paired with sufficiently large degrees. No special handling is required.

Pairs Near the Query Boundary

Some node pairs satisfy:

$$degree(u)+degree(v)>q$$

but

$$degree(u)+degree(v)-count(u,v)\le q$$

These are precisely the false positives created by double-counting shared edges. The correction condition checks exactly this boundary case and subtracts the pair once, ensuring correctness.

Extremely Large Query Values

A query may be close to edges.length. In such cases very few pairs qualify. The two-pointer scan still works correctly because it simply finds fewer degree sums that exceed the threshold. No special cases or overflow concerns arise.

Dense Parallel-Edge Configurations

A graph may contain relatively few node pairs but many repeated edges between them. Since the correction phase iterates over distinct node pairs rather than individual edge occurrences, the implementation remains efficient even when edge multiplicities are large. | Time | O(n log n + m log Q) | Sorting dominates, plus per-edge per-query corrections | | Space | O(n + m) | Degree array and edge frequency map |

The dominant cost is sorting the degree array and iterating over edges for query corrections. Since queries are small (≤ 20), the solution remains efficient.

Test Cases

assert Solution().countPairs(4, [[1,2],[2,4],[1,3],[2,3],[2,1]], [2,3]) == [6,5]  # sample 1
assert Solution().countPairs(5, [[1,5],[1,5],[3,4],[2,5],[1,3],[5,1],[2,3],[2,5]], [1,2,3,4,5]) == [10,10,9,8,6]  # sample 2

# minimum n
assert Solution().countPairs(2, [[1,2]], [0]) == [1]

# disconnected graph
assert Solution().countPairs(4, [], [0,1]) == [6,0]

# heavy multi-edge case
assert Solution().countPairs(3, [[1,2],[1,2],[1,2]], [1,2,3]) == [3,3,2]

Test	Why
sample 1	verifies correctness with duplicate edges
sample 2	dense multi-edge behavior across multiple queries
n=2 single edge	smallest non-trivial graph
no edges	all degrees zero edge case
triple edges	stress multiplicity correction logic

Edge Cases

One important edge case is when the graph contains no edges. In this situation all degrees are zero, so every pair has incident(a, b) = 0. The algorithm correctly returns zero for all queries greater than zero because no pair satisfies the inequality.

Another edge case is when there are many parallel edges between a single pair of nodes. This affects both degree sums and correction logic. Without the correction step, such pairs would be overcounted for many queries. The implementation handles this by explicitly tracking multiplicity and adjusting per query.

A final edge case involves very large degree nodes in a star-shaped graph. Here, most pairs involve the central node, and the two-pointer method efficiently handles the skewed distribution without enumerating all pairs.