Count Pairs Of Nodes: Sorted Degrees and Two Pointers

LeetCode 1782: Count Pairs Of Nodes gives you an undirected graph with n nodes, a list of edges (which may contain duplicates), and an array of queries. For each query q, you need to count the number of pairs (a, b) where a is less than b and the number of edges incident to node a or node b is strictly greater than q. Shared edges between a and b are counted only once.

This is a hard problem that combines degree counting, sorted-array two-pointer sweeps, and a correction step for shared edges. Brute-forcing all pairs for every query would be far too slow, so the solution hinges on a clever trick: overcount first using sorted degrees, then fix the overcounting.

Why this problem matters

Count Pairs Of Nodes teaches you three skills at once. First, you learn how to think about graph queries in terms of node degrees rather than explicit traversals. Second, you see how sorting an array unlocks the two-pointer technique for counting pairs above a threshold. Third, the correction step shows a pattern that comes up whenever an initial calculation overcounts and you need to subtract specific cases back out.

These pieces are useful well beyond this single problem. Degree-based reasoning appears in network analysis, two-pointer counting appears in problems like 3Sum and pair counting on sorted data, and the "overcount then correct" strategy appears in combinatorics problems across many domains.

The key insight

For any pair (a, b), the number of incident edges is degree[a] + degree[b] - shared(a, b), where shared(a, b) is the number of edges that connect a and b directly. The sum degree[a] + degree[b] overcounts because any edge between a and b gets counted once in degree[a] and once in degree[b], but it should only be counted once total.

The key trick: sort a copy of the degree array and use two pointers to count how many pairs have degree[a] + degree[b] > q. This overcounts slightly (it ignores shared edges), but the overcounting only applies to pairs that actually share edges. There are at most E such pairs (one per edge, after deduplication), so you can iterate over them and subtract back the ones that no longer qualify after the correction.

The solution

from collections import Counter

def count_pairs(n, edges, queries):
    degree = [0] * (n + 1)
    shared = Counter()

    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
        shared[min(u, v), max(u, v)] += 1

    sorted_deg = sorted(degree[1:])
    result = []

    for q in queries:
        count = 0
        lo, hi = 0, n - 1

        while lo < hi:
            if sorted_deg[lo] + sorted_deg[hi] > q:
                count += hi - lo
                hi -= 1
            else:
                lo += 1

        for (u, v), s in shared.items():
            if degree[u] + degree[v] > q and degree[u] + degree[v] - s <= q:
                count -= 1

        result.append(count)

    return result

Let's break this down piece by piece.

First, we compute the degree of every node by scanning all edges. For each edge (u, v), both degree[u] and degree[v] increase by one. At the same time, we track shared edges in a Counter keyed by the normalized pair (min(u, v), max(u, v)). This handles duplicate/parallel edges naturally because the counter simply increments.

Next, we sort a copy of the degree array. The original degree array stays untouched because we need it later for the correction step. Sorting is what enables the two-pointer pair-counting technique.

For each query q, we run two pointers (lo starting at the left, hi starting at the right). If sorted_deg[lo] + sorted_deg[hi] > q, then every index between lo and hi also pairs with hi to exceed q (because the array is sorted and all those values are at least as large as sorted_deg[lo]). We add hi - lo to the count and move hi left. Otherwise, we move lo right to try a larger value.

Finally, the correction step. The two-pointer count assumed incident(a, b) = degree[a] + degree[b], but the real value is degree[a] + degree[b] - shared(a, b). Some pairs that passed the > q test using raw degree sums might fail when shared edges are subtracted. For each pair (u, v) that has shared edges, we check: did the raw sum pass but the corrected value does not? If so, we subtract 1.

Visual walkthrough

Here is the algorithm running on a 5-node graph with 6 edges and a query of q = 3.

The walkthrough shows the four phases: degree counting, sorting, two-pointer pair counting, and the correction step where shared edges are checked. The two-pointer phase gives you a fast initial count, and the correction phase adjusts for the handful of pairs where shared edges change the answer.

Complexity analysis

Time: Sorting the degree array takes O(n log n). The two-pointer sweep for each query is O(n), and the correction loop for each query is O(E). With Q queries, the total is O(n log n + Q * (n + E)). In practice E is bounded by the edge list size, and the two-pointer sweep dominates.

Space: The degree array is O(n). The shared-edges counter is O(E) in the worst case (each edge connects a unique pair). The sorted copy of degrees is O(n). Total: O(n + E).

The building blocks

1. Degree counting from an edge list

degree = [0] * (n + 1)
for u, v in edges:
    degree[u] += 1
    degree[v] += 1

This is the most fundamental graph preprocessing step. Every edge contributes 1 to each endpoint's degree. The result tells you how "connected" each node is. Degree arrays show up in problems involving handshaking lemma arguments, Euler paths, and any scenario where you need to reason about node connectivity without running a full traversal.

2. Two-pointer pair counting on a sorted array

sorted_deg = sorted(degree[1:])
lo, hi = 0, n - 1
count = 0
while lo < hi:
    if sorted_deg[lo] + sorted_deg[hi] > q:
        count += hi - lo
        hi -= 1
    else:
        lo += 1

When an array is sorted and you need to count pairs whose sum exceeds a threshold, two pointers give you O(n) time instead of O(n^2). The logic is: if the smallest remaining value plus the largest remaining value exceeds the threshold, then every value between them also pairs with the largest to exceed it. You can count them all at once and move on. This same pattern appears in 3Sum, 3Sum Closest, and Two Sum II.

Edge cases

• No edges: Every node has degree 0. For any query q >= 0, no pair can have incident edges greater than q. Return 0 for all queries. For q that is negative (not typical but worth considering), all pairs qualify.
• All edges between the same two nodes: Shared edge count can be large. The correction step handles this because shared(a, b) reflects the total number of parallel edges.
• Single node: n = 1 means no valid pairs exist (you need a less than b). Return 0 for all queries.
• Query of 0: Almost all pairs with any incident edges qualify. The two-pointer sweep handles this naturally.

From understanding to recall

The algorithm has a satisfying structure: compute degrees, sort, count with two pointers, then correct. Each piece is simple on its own. But under interview pressure, it is easy to forget the correction step or mix up the pointer movement direction. The gap between "I understand how it works" and "I can write it cold" is real.

Spaced repetition helps you close that gap. You practice the degree counting, the two-pointer sweep, and the shared-edge correction as separate building blocks. After a few rounds, the pattern is automatic. When a problem asks you to count pairs above a threshold in a graph, you reach for sorted degrees and two pointers without hesitation.

Related posts

• 3Sum Closest - two-pointer technique on sorted arrays
• Course Schedule - graph with adjacency/degree information
• Find Peak Element - binary search for threshold problems

Count Pairs Of Nodes is a problem where the brute force is obvious but too slow, and the efficient solution combines three well-known building blocks in a clever way. CodeBricks breaks problems like this into their individual pieces, then drills each one with spaced repetition until you can assemble them from memory.