3067. Count Pairs of Connectable Servers in a Weighted Tree Network
Problem Description
In this problem, you are given a set of servers connected by weighted bidirectional edges, which together form an undirected tree graph. Each server is labeled with a unique number from 0
to n-1
, where n
is the number of servers. The connections between them are defined by the edges
, where each edge is represented by a triplet [ai, bi, weighti]
indicating a connection between server ai
and bi
with the weight weighti
. In addition, you have a value signalSpeed
that is used as a divisor to determine connectivity.
The task is to determine for every server in the tree how many pairs of servers (a
and b
) can be connectable through it. Two servers are considered connectable through a third server c
if all of the following conditions are met:
a < b
and botha
andb
are distinct fromc
.- The distance from server
c
toa
is exactly divisible by thesignalSpeed
. - The distance from server
c
tob
is also exactly divisible by thesignalSpeed
. - The paths from
c
toa
andc
tob
do not have common edges.
The result should be an array count
, where count[i]
represents the number of server pairs that are connectable through server i
.
Flowchart Walkthrough
Let’s analyze LeetCode problem 3067 using the provided algorithm flowchart which can be explored further through the Flowchart. Here's a detailed breakdown using the specified flowchart:
-
Is it a graph?
- Yes: The problem describes a network of servers, which can be represented as a graph.
-
Is it a tree?
- Yes: The problem specifically mentions that the network forms a weighted tree.
-
DFS
- Since we have a tree and depth-first search is an efficient way to explore trees, we proceed with DFS to explore the server network and utilize it to count the connectable pairs of servers.
By traversing the servers using the DFS algorithm, we can explore the tree structure while maintaining relevant computational states required to count pairs of connectable servers by comparing attributes like connections or weights, as the problem might suggest.
Conclusion: DFS is the appropriate algorithm to use for this problem, according to the flowchart, due to the structure of the data (a weighted tree) and the need to explore connections recursively between servers.
Intuition
To solve this problem, we devise an approach that leverages Depth-First Search (DFS). We will need to count the number of servers that are at a distance divisible by signalSpeed
from each server, and then we will need to determine how many unique pairs of servers can be formed through that server.
The first step is to represent the network of servers using an adjacency list g
, which will allow us to traverse the graph efficiently and find the neighbors of any given server.
Next, for each server a
, we can consider it as a potential intermediate connecting server. Starting from a
, we visit all directly connected neighbors b
using DFS. While traversing the graph, we keep accumulating the count of nodes reachable from a
via b
at distances that are divisible by signalSpeed
. We perform this count by invoking dfs(b, a, w)
where b
is the neighbor node, a
is the current node, and w
is the weight of the edge connecting them.
As we move through the tree, we keep a cumulative count s
of nodes reachable from previous neighbors. When we calculate the count t
for a new neighbor, we update the number of connectable server pairs for server a
by adding s * t
to it. This represents the number of new unique pairs that can be formed by combining servers reachable from previous neighbors with servers reachable from the current neighbor. After evaluating all neighbors of a
, we will have the total number of connectable server pairs through a
.
After iterating through all servers in this manner, we obtain the desired count of connectable server pairs for each server, which we return as the result.
Learn more about Tree and Depth-First Search patterns.
Solution Approach
The solution approach uses Depth-First Search (DFS) which is a common algorithm for traversing or searching through tree structures. DFS is a good fit for this problem because it allows us to explore all the paths from a given server to its descendent servers, thereby calculating distances and checking divisibility by signalSpeed
.
Here's how the algorithm is implemented:
-
Construct an adjacency list
g
; for each edge[a, b, w]
in theedges
list, add an entry such thatg[a]
includes the tuple(b, w)
, representing a neighborb
and the weight of the edgew
froma
tob
, and vice versa since it's an undirected graph. -
Create an array
ans
initialized with zeros to store the resulting counts of connectable server pairs for each server. -
For each server
a
, we want to find the number of connectable server pairs that includea
as an intermediate server. -
Initialize a count
s
to 0, representing the cumulative count of servers found through previous neighbors of servera
. -
For each neighbor
b
with edge weightw
connected toa
:- Perform a DFS to calculate the number
t
of servers connectable starting fromb
such that the distance toa
(accumulated in a variablews
within the DFS) is divisible bysignalSpeed
. - The DFS function
dfs(a, fa, ws)
receives the current servera
, its parent serverfa
, and the current weight sumws
. The function returns the number of servers reachable froma
with the sum of edge weights divisible bysignalSpeed
.
- Perform a DFS to calculate the number
-
Use the count
t
from the DFS to update the answer for the current servera
. The number of new connectable pairs iss * t
because each server counted bys
can form a pair with each server counted byt
. Add this number toans[a]
. -
Update the cumulative count
s
by addingt
to it, for the next iterations. This step is crucial because it accumulates the total number of servers that can be connected througha
from all its neighbors. -
After computing this for all neighbors
b
of a servera
, you end up with the total count of server pairs that can connect througha
, stored inans[a]
. -
Repeat steps 4-8 for each server in the graph to fill the array
ans
with the total count of connectable server pairs for all servers. -
Return the array
ans
which now contains the required result for each server in the tree.
This algorithm works efficiently due to the tree's properties, which ensure there are no cycles, and each distinct path from a node a
to any other nodes in its subtree can be explored exactly once by DFS without revisiting nodes, thus avoiding redundant calculations, and enabling the solution approach to work in polynomial time complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example with 4 servers and signalSpeed = 2
to illustrate the solution approach.
Servers (number of servers, n): 4 signalSpeed: 2 edges: [[0, 1, 2], [1, 2, 4], [1, 3, 2]]
Our tree graph for servers will look like this:
0 | |(weight: 2) | 1 / \ / \ / \ 2 3 (weight: 4) (weight: 2)
Step 1: Construct the adjacency list g
from the edges:
g[0] = [(1, 2)] g[1] = [(0, 2), (2, 4), (3, 2)] g[2] = [(1, 4)] g[3] = [(1, 2)]
Step 2: Initialize an array ans
with zeros [0, 0, 0, 0]
to hold the counts for each server.
Step 3: We'll iterate over each server to find the number of connectable server pairs.
Step 4-7: For server 0
, the neighbor is server 1
with an edge weight of 2
, we perform a DFS starting from server 1
. Since we are only interested in servers that are connectable through server 0
, we find servers 2
and 3
are both reachable from 1
with distances divisible by signalSpeed = 2
. Since server 1
has two connectable servers, there is only one pair (2, 3)
that can be routed through it. So we add 1
to ans[0]
.
Step 4-7: For server 1
, we see three potential paths (one through 0
, one through 2
, and one through 3
). Through DFS for each neighbor, we find the following:
- Server
0
contributes 0 connectable servers. - Server
2
contributes 1 connectable server (itself). - Server
3
contributes 1 connectable server (itself). Combining the paths from2
and3
, as2 < 3
, gives us 1 pair. Hence, we add1
toans[1]
.
Servers 2
and 3
have only one neighbor they connect to without common edges, which is server 1
, and no server pairs (a, b)
such that a < b
are connectable through them. Hence, ans[2]
and ans[3]
remain 0
.
Step 9: After iterating over all servers, the ans
array values are finalized as [1, 1, 0, 0]
.
Step 10: The final output [1, 1, 0, 0]
is returned, indicating that through server 0
, 1 pair of servers can be connected, the same for server 1
, and no connectable pairs through servers 2
and 3
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def countPairsOfConnectableServers(
5 self, connections: List[List[int]], signal_speed: int
6 ) -> List[int]:
7 # Helper function to perform depth-first search and count the number of pairs
8 def dfs(node: int, parent: int, total_weight: int) -> int:
9 pair_count = 1 if total_weight % signal_speed == 0 else 0
10 for neighbor, weight in graph[node]:
11 if neighbor != parent:
12 pair_count += dfs(neighbor, node, total_weight + weight)
13 return pair_count
14
15 # Calculate the total number of nodes (servers)
16 num_nodes = len(connections) + 1
17 # Initialize a graph from the connection data
18 graph = [[] for _ in range(num_nodes)]
19 for src, dest, weight in connections:
20 graph[src].append((dest, weight))
21 graph[dest].append((src, weight))
22
23 # Initialize a list to store the answer for each node
24 answer = [0] * num_nodes
25 # Loop through each node to find count of connectable server pairs
26 for node in range(num_nodes):
27 cumulative_pairs = 0
28 # Iterate over the connections for the current node
29 for neighbor, weight in graph[node]:
30 # Count pairs for each connection
31 pairs = dfs(neighbor, node, weight)
32 # Update the answer list using the half-pair technique
33 answer[node] += cumulative_pairs * pairs
34 # Update the cumulative count of pairs for the next connections
35 cumulative_pairs += pairs
36 return answer
37
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6 private int signalSpeed; // The speed of the signal as defined.
7 private List<int[]>[] adjacencyList; // This list represents the graph as an adjacency list.
8
9 // Method to count pairs of connectable servers given the edges and signal speed.
10 public int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {
11 int numServers = edges.length + 1; // Number of servers is one more than the number of edges.
12 this.signalSpeed = signalSpeed; // Set the global signal speed.
13 adjacencyList = new List[numServers]; // Initialize the adjacency list for each server.
14 Arrays.setAll(adjacencyList, x -> new ArrayList<>());
15 // Convert the edge list to an adjacency list representation of the graph.
16 for (int[] edge : edges) {
17 int from = edge[0], to = edge[1], weight = edge[2];
18 adjacencyList[from].add(new int[] {to, weight});
19 adjacencyList[to].add(new int[] {from, weight});
20 }
21 int[] answer = new int[numServers]; // Initialize an array to store the counts for each server.
22 // Iterate over each server to find connectable pairs by using depth-first search.
23 for (int server = 0; server < numServers; ++server) {
24 int count = 0;
25 // Explore all reachable servers from the current one and calculate counts.
26 for (int[] edge : adjacencyList[server]) {
27 int neighbor = edge[0], weight = edge[1];
28 int reachableServers = dfs(neighbor, server, weight);
29 answer[server] += count * reachableServers;
30 count += reachableServers;
31 }
32 }
33 return answer; // Return the answer array containing counts for each server.
34 }
35
36 // Helper method for depth-first search to count reachable servers given a certain accumulated weight.
37 private int dfs(int current, int parent, int accumulatedWeight) {
38 // If the accumulated weight is a multiple of the signal speed, it means this server is connectable.
39 int connectableServers = accumulatedWeight % signalSpeed == 0 ? 1 : 0;
40 // Explore all connected servers from the current server.
41 for (int[] edge : adjacencyList[current]) {
42 int nextServer = edge[0], weight = edge[1];
43 // Avoid visiting the server from which the current DFS initiated.
44 if (nextServer != parent) {
45 connectableServers += dfs(nextServer, current, accumulatedWeight + weight);
46 }
47 }
48 return connectableServers; // Return the count of reachable connectable servers.
49 }
50}
51
1#include <vector>
2#include <functional>
3using namespace std;
4
5class Solution {
6public:
7 vector<int> countPairsOfConnectableServers(vector<vector<int>>& edges, int signalSpeed) {
8 // Determine the number of servers in the network (nodes in the graph)
9 int numServers = edges.size() + 1;
10
11 // Create a graph represented as an adjacency list with pairs of connected server and link weight
12 vector<pair<int, int>> graph[numServers];
13
14 // Populate the graph with the given edges and their weights
15 for (auto& edge : edges) {
16 int serverA = edge[0], serverB = edge[1], weight = edge[2];
17 graph[serverA].emplace_back(serverB, weight);
18 graph[serverB].emplace_back(serverA, weight);
19 }
20
21 // Lambda function for depth-first search to count connectable pairs
22 function<int(int, int, int)> dfs = [&](int server, int parent, int cumulativeWeight) {
23 // Count the server as connectable if the cumulative weight is multiple of signalSpeed
24 int count = cumulativeWeight % signalSpeed == 0;
25 // Traverse the connected servers
26 for (auto& [connectedServer, edgeWeight] : graph[server]) {
27 if (connectedServer != parent) {
28 // Add the count of connectable servers in the subtree
29 count += dfs(connectedServer, server, cumulativeWeight + edgeWeight);
30 }
31 }
32 return count;
33 };
34
35 // Vector to store the count of connectable pairs of servers for each server
36 vector<int> counts(numServers);
37
38 // Iterate through each server to calculate the connectable pairs
39 for (int server = 0; server < numServers; ++server) {
40 int connectableCount = 0;
41 // Iterate through the connected servers and add to the pair count
42 for (auto& [connectedServer, edgeWeight] : graph[server]) {
43 int tempCount = dfs(connectedServer, server, edgeWeight);
44 counts[server] += connectableCount * tempCount;
45 // Update the connectable count with the recently found count
46 connectableCount += tempCount;
47 }
48 }
49
50 // Return the vector containing counts for each server
51 return counts;
52 }
53};
54
1function countPairsOfConnectableServers(edges: number[][], signalSpeed: number): number[] {
2 // n represents the total number of servers.
3 const numServers = edges.length + 1;
4 // graph is used to store the connectivity information as an adjacency list.
5 const graph: [number, number][][] = Array.from({ length: numServers }, () => []);
6
7 // Convert the edge list into an adjacency list.
8 for (const [from, to, weight] of edges) {
9 graph[from].push([to, weight]);
10 graph[to].push([from, weight]);
11 }
12
13 // Depth-first search function to count the number of times the sum of weights is divisible by the signal speed.
14 const depthFirstSearch = (current: number, parent: number, totalWeight: number): number => {
15 let count = totalWeight % signalSpeed === 0 ? 1 : 0;
16 for (const [neighbor, weight] of graph[current]) {
17 if (neighbor !== parent) {
18 count += depthFirstSearch(neighbor, current, totalWeight + weight);
19 }
20 }
21 return count;
22 };
23
24 // Initialize an array to hold the answers.
25 const answer: number[] = Array(numServers).fill(0);
26
27 // Iterate over each server to compute pairs of connectable servers.
28 for (let server = 0; server < numServers; ++server) {
29 let subCount = 0;
30 for (const [neighbor, weight] of graph[server]) {
31 const countFromNeighbor = depthFirstSearch(neighbor, server, weight);
32 answer[server] += subCount * countFromNeighbor;
33 subCount += countFromNeighbor;
34 }
35 }
36
37 // Return the answer array.
38 return answer;
39}
40
Time and Space Complexity
The time complexity of the given code is O(n^2)
. This is because for each of the n
nodes, there is a Depth-First Search (DFS) that is initiated. DFS itself may visit each node one time in the worst case, and since the DFS is occurring in a loop of n
nodes, this results in a potential of n * (n-1)
operations, hence the O(n^2)
.
Furthermore, within the DFS function, there is a check for whether ws % signalSpeed
is equal to zero that occurs with each recursive call, but this does not add to the complexity in terms of n
, as it is a constant-time operation.
The space complexity of the code is O(n)
. The primary space usage comes from the adjacency list g
, which contains a list for each of the n
nodes. Each list hold pairs ((b, w)
) representing edges and their weights. There is also the ans
array of size n
that is kept throughout the execution. Temporary variables such as cnt
and the stack frames due to recursive calls do not increase the overall space complexity, as they will at most be proportional to the depth of the recursion which is at most n
, in the case of a path graph.
Additionally, the recursive nature of the DFS function does entail a call stack, which could have a depth of up to n
in a worst-case scenario (such as a linear tree), but since the adjacency list is the dominant space-consuming structure and they are both of O(n)
space complexity, the overall space complexity remains O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!