This is our solution and implementation to problem #1782: Count Pairs Of Nodes on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Count Pairs Of Nodes on LeetCode.
Problem Analysis
The input of the problem will be:
- n: the total number of nodes we'll be working with:
- edges: an array of each edge in the graph.
- queries: an array of ints representing queries.
The problem defines incident(a, b) as the number of edges that are connected to either node a or node b.
A query asks: "how many pairs of nodes (a, b) satisfy the following":
- a < b.
- incident(a, b) > query value.
There are a few cases the implementation will need to account for:
- We can have more than one instance of the same edge (a, b).
- For each edge (a, b), we may or may not have an edge (b, a).
- We may have queries which have an answer of 0, or the maximum possible answer.
- Multiple queries might have the same answer.
- For incident(a, b), we need to make sure not to count any edges twice.
In order to calculate incident(a, b), we'll need to know the degree of nodes a and b. We'll also need to be sure not to count any edges twice. We can do this by keeping track of the degree of each edge. The full calculation: incident(a, b) = nodeDegree[a] + nodeDegree[b] - edgeDegree[a, b]. Once we have a way of calculating incident(a, b), we can use this to calculate the answers for each query. To avoid redundant iteration, we will need to use additional space to store the degrees of each node + edge; otherwise, we would need to re-calculate them for each query.
Implementation Strategy
Our algorithm will split the main problem into a series of subproblems:
- Determine the degree of each node and store in nodeDegrees.
- Determine the degree of each edge and store in edgeDegrees.
- Make a new array sortedDegrees which is a sorted version of nodeDegrees.
- Create an answers array, where answers[i] is the answer to queries[i].
- For each query, use the data above to calculate how many pairs (a, b) satisfy a query. Store each queries[i] result in answers[i].
To determine the values for nodeDegrees, we need to create a mapping of node values to the number of connections they have. Since we are told by the problem all node values are 1...n, we can use an ArrayList. To determine the values for edgeDegrees, we'll need to create a mapping of pairs (a, b) to the number of edges which touch both of those elements (meaning (a, b) and (b, a)). We will use a HashMap of HashMaps for this purpose. The outer key will be the a node, the inner key will be the b node, and the value will be the number of edges. For consistency, we'll store and use the keys such that the outer key is always less than the inner key.
With these data structures in place, we'll populate nodeDegrees and edgeDegrees via the steps below. For each (a, b) in the given edges:
- Increment nodeDegrees[a].
- Increment nodeDegrees[b].
- Increment edgeDegrees[a][b].
- Note that in the actual Java code, we'll need to be sure to create the submap for edgeDegrees(a) if it doesn't already exist at each point.
Once the values are in place, we'll copy nodeDegrees into sortedDegrees and sort that array using Java's built-in Arrays.sort().
Next, we'll iterate over the queries to populate our anwers. For each query, our implementation will determine an upper bounds for the number of satisfying incident pairs by using sortedDegrees, then refine the answer by removing any edges which were considered more than once by utilizing the data in edgeDegrees. To determine the upper bound, the algorithm will use two pointers to iterate over the sortedDegrees:
- Pointer left is initialized to 1, not 0 because there is no 0 node.
- Pointer right is initialized to n.
- We'll be adjusting these pointers throughout the following loop. While right > left:
- Take the sum of sortedDegrees[left] + sortedDegrees[right].
- If sum > query, we've just found a pair which satisfies the query:
- Add right - left to the current value of count.
- Decrement right.
- If not, increment left.
The algorithm above searches for pairs (a, b) such that increment(a, b) is possibly greater than query. To be sure, we'll need to traverse the edges to ensure we haven't counted any edge more than once. For each (a, b) in edgeDegrees:
- Set sumDegree to nodeDegrees[a] + nodeDegrees[b]. This is similar to what we were looking for in the previous loop.
- Set adjustedDegree to sumDegree - edgeDegrees[a][b]. This is the true value of incidents(a, b).
- If sumDegree was included in the count, meaning sumDegree > query, but adjustedDegree < query, decrement count.
At the end, set answers[i] = count.
Space and Time Complexity
The space complexity is O(n + e + q). We'll be using an array of size n, a map with e key-value pairs, and an array of size q for the answers (though we could also overwrite the queries array to save that space if we needed to). The time complexity is O(q⋅(n+e)). Determining the degrees of the nodes + edges takes O(n) time, then for each query, we iterate over the sorted list of node degrees, which takes O(n) time, then iterate over the list of edge degrees, which takes O(e) time.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java files below. This solution uses more than one code file. The Main.java file is used as a runner to test locally and includes a few test cases, some from the examples provided by LeetCode and some designed for our own test purposes. The Solution.java file contains the main logic for the solution.
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.