We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Pairs Of Nodes

Number: 1891

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an undirected graph with n nodes and a list of edges (which may contain duplicate pairs), for any two distinct nodes a and b (with a < b), the "incident" score is defined as the total number of edges connected to either node including duplicates. For each query value in a set of queries, we must count the number of pairs (a, b) such that the incident count is greater than the query value.

Key Insights

  • Compute the degree for each node; note that duplicate edges will increase node degrees.
  • Count the number of direct connections between each unique pair (using a map or dictionary) because a and b might be connected by multiple edges.
  • Sort the degree array to leverage two pointers or binary search for efficient counting.
  • For any pair (a, b), the total incident count is degree[a] + degree[b] minus the number of duplicate edges between them.
  • For each query, count all pairs that satisfy degree[a] + degree[b] > query initially then subtract those pairs where the direct connection count causes an overcount.
  • Adjusting with the direct connection count is a critical gotcha.

Space and Time Complexity

Time Complexity: O(m + n log n + q * n) in the worst-case scenario, where m is the number of edges, n is the number of nodes, and q is the number of queries. (Note: With careful implementation and two pointers/binary search, much of the inner loop can be optimized.) Space Complexity: O(n + m), for storing the degree array and the mapping of direct edge counts.

Solution

We start by computing the degree for each node from all edges. Simultaneously, we use a hash map to count the number of direct (possibly duplicate) connections between each unique pair (ordered so that a < b). Once the degrees are computed, we sort the degree list. For each query, we use a two‐pointers technique on the sorted degrees to count the number of pairs (i, j) where degree[i] + degree[j] > query. However, some pairs might have been over-counted because of multiple direct connections between them; for each such pair, if degree[i] + degree[j] > query but degree[i] + degree[j] - directConnections <= query, we decrease the count. This ensures that only the valid pairs are counted. The result for each query is stored and returned in order.

Code Solutions

# Python solution with detailed comments
from collections import defaultdict
from bisect import bisect_right

def countPairs(n, edges, queries):
    # degree: count degree (consider multiple edges)
    degree = [0] * (n + 1)
    # using dictionary to count direct connections between pairs (i, j) with i < j
    direct = defaultdict(int)
    
    # Process each edge: update degrees and direct connection count
    for u, v in edges:
        degree[u] += 1
        degree[v] += 1
        a, b = min(u, v), max(u, v)
        direct[(a, b)] += 1

    # We only need degrees for nodes 1..n
    sorted_deg = sorted(degree[1:])

    ans = []
    # Process each query individually
    for q in queries:
        total_pairs = 0
        # Two pointers approach over sorted degrees useful for counting pairs with sum > q
        l, r = 0, n - 1
        while l < r:
            if sorted_deg[l] + sorted_deg[r] > q:
                total_pairs += (r - l)
                r -= 1
            else:
                l += 1

        # Adjust total_pairs by subtracting pairs that were overcounted due to direct connections
        for (u, v), cnt in direct.items():
            # If the pair was initially counted but should not be,
            # i.e. if removing the extra direct count makes the pair fail the query condition.
            if degree[u] + degree[v] > q and degree[u] + degree[v] - cnt <= q:
                total_pairs -= 1

        ans.append(total_pairs)
    return ans

# Example usage:
n = 4
edges = [[1,2],[2,4],[1,3],[2,3],[2,1]]
queries = [2,3]
print(countPairs(n, edges, queries))  # Expected output: [6, 5]
← Back to All Questions