1782. Count Pairs Of Nodes

HardGraphArrayTwo PointersBinary SearchSorting
Leetcode Link

Problem Description

The problem presents an undirected graph with n nodes and a list of edges, where each edge [u_i, v_i] represents an undirected connection between nodes u_i and v_i. Along with the graph, there is also an array of queries. The challenge is to compute, for each query, the number of unique pairs of nodes (a, b) that satisfy the following conditions:

  1. a is less than b (to avoid duplication since the graph is undirected).
  2. The number of edges connected to either node a or node b is greater than the value of the current query.

This is not as straightforward as simply iterating over all pairs of nodes, because the number of possible pairs increases quadratically with the number of nodes, which would result in an inefficient solution.

Intuition

The intuition behind the solution approach is to use a combination of sorting, binary search, and careful counting to efficiently find the number of node pairs (a, b) that meet the criteria for each query.

  1. Count the incident edges: The first step is to count the number of edges incident to each node. This count is later used to determine if a pair of nodes (a, b) has more incidents than the query value.

  2. Sort the counts: By sorting the counts of incident edges, we can then use binary search to quickly identify how many nodes have a count of incidents greater or equal to what is needed for a specific query.

  3. Binary search to find pairs: For each node j, binary search is used to find how many nodes k have enough incidents such that the sum of incidents for nodes j and k is greater than the query value.

  4. Adjust for exact matches: Since multiple edges can exist between the same two nodes, we must adjust the pairs count if the exact sum of incidents equals the query value after removing the redundant edges (hence why the adjustment checks if removing the shared edge from the total incidents would fall at or below the query value).

Combining these steps allows us to programmatically calculate the output for all queries in a way that is much more efficient than brute force, enabling the solution to handle larger graphs and queries within acceptable time constraints.

Learn more about Graph, Two Pointers, Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The solution code implements the following approach:

  1. Initialize Counters: Initialize a counter list cnt with a size equal to the number of nodes. This list will keep track of the number of edges connected to each node. Also, create a dictionary g, which will hold the counts of edges between each distinct node pair (used for adjustment later).

  2. Count Edges and Pairs: Iterate over the list of edges. For each edge (a, b), sort the nodes to ensure that a < b (since the graph is undirected) and increase their respective counters in cnt. Also, keep a running total of edges between the specific pair in the g dictionary.

  3. Sort Node Incidents: Sort the cnt array containing the incidents count for all nodes. This is crucial as it allows us to use binary search in the next step to quickly find eligible pairs for each query.

  4. Processing Queries: Each query asks how many pairs (a, b) there are such that incident(a, b) > queries[j]. To answer this, loop through each query in queries. For each node count x in the sorted cnt list:

    • Use binary search bisect_right to find the boundary k where any node beyond this index k in the sorted list when paired with the current node j, will have a combined incident count greater than the query value. This effectively counts eligible pairs (j, k) for the query, as node k to the end of the sorted list would satisfy the query.
    • The difference n - k gives the number of possible pairs for that node. Accumulate these values in ans[i] for the i-th query.

  5. Adjustment for Shared Edges: After summing up all probable pairs, we must subtract those pairs (a, b) where the incident count is only greater than the query after including the shared edges. Thus, for each pair (a, b) in the g dictionary, if the sum of their individual incidents cnt[a] + cnt[b] is greater than the query but no longer greater than the query after subtracting the shared edge count v, decrement the answer for that query since we've initially overcounted this pair.

  6. Return Results: After processing all queries and making all necessary adjustments, return the list ans containing the number of valid pairs for each query.

This approach utilizes a combination of counting, sorting, and binary searching to resolve the "pairs with greater incidents than" problem effectively within a polynomial complexity, avoiding a naive quadratic pairing which would be inefficient at scale.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Suppose our graph has n = 4 nodes and the following list of edges = [[1, 2], [2, 3], [2, 4], [1, 3]]. We have an array of queries queries = [1, 2] that we need to answer according to the solution approach described above.

  1. Initialize Counters

    • Initialize the cnt array to store the number of edges incident to each node: cnt = [0, 0, 0, 0] because we have 4 nodes.
    • Initialize a dictionary g to store the counts of edges between each pair of nodes: g = {}.

  2. Count Edges and Pairs

    • For the edge [1, 2], we increment cnt[0] and cnt[1] by 1 (assuming 1-based indexing for cnt: cnt = [1, 1, 0, 0]) and add g[(1, 2)] = 1.
    • For the edge [2, 3], increment cnt[1] and cnt[2], resulting in cnt = [1, 2, 1, 0] and g[(2, 3)] = 1.
    • For the edge [2, 4], increment cnt[1] and cnt[3], leading to cnt = [1, 3, 1, 1] and g[(2, 4)] = 1.
    • For the edge [1, 3], increment cnt[0] and cnt[2], getting cnt = [2, 3, 2, 1], and add g[(1, 3)] = 1.

  3. Sort Node Incidents

    • We sort cnt to get sorted_cnt = [1, 1, 2, 3].

  4. Processing Queries

    • Process each query q from queries. For q = 1, find pairs (a, b) where incident(a, b) > q. We loop over sorted_cnt and use binary search:
      • For node with 1 incident, bisect_right finds no other nodes with incidents higher than q - 1 = 0, so no pairs are added.
      • For the next node with 1 incident, the same occurs. Still no pairs added.
      • For the node with 2 incidents, bisect_right will return index 3 (1-based), meaning there's 1 node satisfying the condition (the node with 3 incidents). We add this pair, and ans[0] = 1.
      • For the node with 3 incidents, bisect_right will return 4, but since it includes the node itself, we don't count it.
    • For the second query q = 2, repeat the process:
      • For nodes with 1 incident, bisect_right now finds indices 3 and 4 as q - 1 = 1, so two more pairs for ans[1].
      • For the node with 2 incidents, bisect_right finds index 4, so one more pair, and we have ans[1] = 3.

  5. Adjustment for Shared Edges

    • There are no shared edges, so no adjustments are needed in this example.

  6. Return Results

    • After processing all queries, we have the results for the queries. The answer to the query q = 1 is ans[0] = 1 and for q = 2 is ans[1] = 3.
    • Return ans = [1, 3].

Given our small graph and queries, the returned answers indicate there is one pair of nodes with more than one incident edge for the first query and three pairs for the second query.

Solution Implementation

1from collections import defaultdict
2from bisect import bisect_right
3from typing import List
4
5class Solution:
6    def countPairs(self, n: int, edges: List[List[int]], queries: List[int]) -> List[int]:
7        # Initialize a list to store the count of edges each node is connected to
8        edge_count = [0] * n
9        # Dictionary to store the count of shared edges between pairs of nodes
10        shared_edges_count = defaultdict(int)
11
12        # Calculate the edge count and shared edges count
13        for a, b in edges:
14            # Decrement to convert to 0-indexed and identify the smaller node
15            a, b = a - 1, b - 1
16            a, b = min(a, b), max(a, b)
17            edge_count[a] += 1
18            edge_count[b] += 1
19            shared_edges_count[(a, b)] += 1
20
21        # Sort the edge counts
22        sorted_edge_count = sorted(edge_count)
23        # Initialize the answer list for each query
24        answer = [0] * len(queries)
25
26        # Process each query
27        for i, threshold in enumerate(queries):
28            # For each node in sorted order, count nodes with enough edges to exceed the threshold
29            for j, edge_cnt in enumerate(sorted_edge_count):
30                # Find the rightmost value greater than the remaining threshold to satisfy the query
31                k = bisect_right(sorted_edge_count, threshold - edge_cnt, lo=j + 1)
32                # Add the number of nodes with enough edges to the answer
33                answer[i] += n - k
34            # Adjust the answer for shared edges
35            for (a, b), shared_edges in shared_edges_count.items():
36                if edge_count[a] + edge_count[b] > threshold and edge_count[a] + edge_count[b] - shared_edges <= threshold:
37                    answer[i] -= 1
38        return answer
39
1class Solution {
2    // Method to count pairs based on given queries
3    public int[] countPairs(int n, int[][] edges, int[] queries) {
4        // Degree count for each node
5        int[] degreeCount = new int[n];
6        // Map to store the number of shared edges between nodes
7        Map<Integer, Integer> sharedEdges = new HashMap<>();
8      
9        // Count the degrees and shared edges
10        for (int[] edge : edges) {
11            int a = edge[0] - 1;
12            int b = edge[1] - 1;
13            degreeCount[a]++;
14            degreeCount[b]++;
15            int key = Math.min(a, b) * n + Math.max(a, b);
16            sharedEdges.merge(key, 1, Integer::sum);
17        }
18      
19        // Sort the degrees for binary searching later
20        int[] sortedDegrees = degreeCount.clone();
21        Arrays.sort(sortedDegrees);
22      
23        // Answer array to store result for each query
24        int[] answer = new int[queries.length];
25      
26        // Process each query
27        for (int i = 0; i < queries.length; i++) {
28            int queryThreshold = queries[i];
29          
30            // Two pointers approach to find valid pairs
31            for (int j = 0; j < n; j++) {
32                int currentValue = sortedDegrees[j];
33                int k = search(sortedDegrees, queryThreshold - currentValue, j + 1);
34                answer[i] += n - k;
35            }
36          
37            // Adjust answer for edges that were counted twice
38            for (var entry : sharedEdges.entrySet()) {
39                int a = entry.getKey() / n;
40                int b = entry.getKey() % n;
41                int commonEdges = entry.getValue();
42              
43                // If the actual pair was counted, remove it if it shouldn't be
44                if (degreeCount[a] + degreeCount[b] > queryThreshold 
45                    && degreeCount[a] + degreeCount[b] - commonEdges <= queryThreshold) {
46                    answer[i]--;
47                }
48            }
49        }
50        return answer;
51    }
52
53    // Helper method for binary search to find the right position
54    private int search(int[] arr, int x, int start) {
55        int left = start, right = arr.length;
56        while (left < right) {
57            int mid = (left + right) / 2;
58            if (arr[mid] > x) {
59                right = mid;
60            } else {
61                left = mid + 1;
62            }
63        }
64        return left;
65    }
66}
67
1class Solution {
2public:
3    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
4        vector<int> nodeDegree(n); // This vector holds the degree of each node.
5        unordered_map<int, int> sharedEdgesCount; // This map will hold the number of shared edges between pairs of nodes.
6
7        // Go through each edge and update degree count and shared edges for the pair.
8        for (auto& edge : edges) {
9            int node1 = edge[0] - 1;
10            int node2 = edge[1] - 1;
11            ++nodeDegree[node1];
12            ++nodeDegree[node2];
13            int combinedKey = min(node1, node2) * n + max(node1, node2); // Unique key for each node pair.
14            ++sharedEdgesCount[combinedKey];
15        }
16
17        vector<int> sortedDegrees = nodeDegree; // We'll need a sorted version of the degrees for two-pointer technique.
18        sort(sortedDegrees.begin(), sortedDegrees.end());
19      
20        vector<int> answer(queries.size()); // This will hold our final answer for each query.
21
22        // For each query, count the valid pairs.
23        for (int i = 0; i < queries.size(); ++i) {
24            int threshold = queries[i];
25
26            // Using the two-pointer technique to find valid pairs by degree sum.
27            for (int j = 0; j < n; ++j) {
28                int degree = sortedDegrees[j]; // Choose a starting degree from sorted array.
29                // Find the position of the smallest element that, when added to `degree`,
30                // would exceed `threshold`. Subtract from total nodes to get count.
31                int pairsCount = upper_bound(sortedDegrees.begin() + j + 1, sortedDegrees.end(), threshold - degree) - sortedDegrees.begin();
32                answer[i] += n - pairsCount;
33            }
34
35            // Adjust answer based on shared edges between node pairs.
36            for (auto& [combinedKey, sharedEdges] : sharedEdgesCount) {
37                int node1 = combinedKey / n;
38                int node2 = combinedKey % n;
39                // If sum of degrees of nodes exceeds threshold but subtracting shared edges doesn't,
40                // we've previously counted this as a valid pair incorrectly and must decrement.
41                if (nodeDegree[node1] + nodeDegree[node2] > threshold && nodeDegree[node1] + nodeDegree[node2] - sharedEdges <= threshold) {
42                    --answer[i];
43                }
44            }
45        }
46        return answer; // Return the final counts of valid pairs for each query.
47    }
48};
49
1function countPairs(nodeCount: number, graphEdges: number[][], queryValues: number[]): number[] {
2    // Initialize counter for each node with zero
3    const edgeCounts: number[] = new Array(nodeCount).fill(0);
4  
5    // Map for counting shared edges
6    const sharedEdgeCounts: Map<number, number> = new Map();
7  
8    // Fill edge counts and shared edges
9    for (const [node1, node2] of graphEdges) {
10        edgeCounts[node1 - 1]++;
11        edgeCounts[node2 - 1]++;
12        const key = Math.min(node1 - 1, node2 - 1) * nodeCount + Math.max(node1 - 1, node2 - 1);
13        sharedEdgeCounts.set(key, (sharedEdgeCounts.get(key) || 0) + 1);
14    }
15  
16    // Sort edge counts in ascending order
17    const sortedEdgeCounts = [...edgeCounts].sort((a, b) => a - b);
18  
19    // Binary search utility function
20    const binarySearch = (values: number[], target: number, left: number): number => {
21        let right = values.length;
22        while (left < right) {
23            const mid = (left + right) >> 1;
24            if (values[mid] > target) {
25                right = mid;
26            } else {
27                left = mid + 1;
28            }
29        }
30        return left;
31    };
32  
33    // Initialize the resultant array
34    const results: number[] = [];
35  
36    // For each query, calculate the number of valid pairs
37    for (const threshold of queryValues) {
38        let pairCount = 0;
39        for (let index = 0; index < sortedEdgeCounts.length; ++index) {
40            const searchResult = binarySearch(sortedEdgeCounts, threshold - sortedEdgeCounts[index], index + 1);
41            pairCount += nodeCount - searchResult;
42        }
43      
44        // Adjust the count for shared edges
45        for (const [key, sharedCount] of sharedEdgeCounts) {
46            const node1 = Math.floor(key / nodeCount);
47            const node2 = key % nodeCount;
48            if (edgeCounts[node1] + edgeCounts[node2] > threshold && edgeCounts[node1] + edgeCounts[node2] - sharedCount <= threshold) {
49                --pairCount;
50            }
51        }
52      
53        // Add the final result for this query
54        results.push(pairCount);
55    }
56  
57    // Return the array of results for all queries
58    return results;
59}
60
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

Time Complexity

The time complexity of the code involves several parts:

  1. Creating and populating the graph and count array: Iterating over each edge to populate the cnt and g has a time complexity of O(E) where E is the number of edges.

  2. Sorting the cnt array: Sorting the array of nodes' degrees has a time complexity of O(N log N) where N is the number of nodes.

  3. Processing queries: For each query, the code iterates over each possible x in s (the sorted cnt array) and then performs a binary search to find k which has a time complexity of O(log N). Since this is inside a loop that goes through s, the complexity of this part becomes O(N log N).

  4. Adjusting count for each query based on the graph g dictionary: This step involves iterating over each item in g (which would be at most E, the number of unique edges) for each query, giving it a complexity of O(Q * E) where Q is the number of queries.

Combining these parts, the overall time complexity is O(E) + O(N log N) + O(Q * (N log N + E)), which simplifies to O(Q * (N log N + E)) assuming Q * N log N dominates E and Q * E dominates N log N.

Space Complexity

The space complexity of the code is influenced by the following components:

  1. The cnt array: Requires O(N) space.

  2. The g graph representation: In the worst case, it stores all the unique edges, so it takes O(E) space.

  3. The s array: It’s a sorted list of node degrees, which also requires O(N) space.

  4. The ans array: This requires O(Q) space, where Q is the number of queries.

  5. Auxiliary space for sorting: Sorting an array in Python requires O(N) space.

Therefore, the overall space complexity is O(N + E + Q + N), simplifying to O(N + E + Q) when not considering the coefficients.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Recommended Readings

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫