Scale Engineer

Count Pairs of Connectable Servers in a Weighted Tree Network

Med
#2723Time: O(N^3). The main loop runs `N` times. Inside, the traversal takes O(N). The nested loops to check all pairs `(a, b)` take O(N^2). Thus, the total complexity is O(N * (N + N^2)) = O(N^3), which is too slow for the given constraints.Space: O(N) to store the adjacency list, a distance array, and a first-hop array for each central server.2 companies
Algorithms
Depth-First Search
Data structures
ArrayTree
Companies
UBSthoughtspot

Prompt

You are given an unrooted weighted tree with n vertices representing servers numbered from 0 to n - 1, an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional edge between vertices ai and bi of weight weighti. You are also given an integer signalSpeed.

Two servers a and b are connectable through a server c if:

  • a < b, a != c and b != c.
  • The distance from c to a is divisible by signalSpeed.
  • The distance from c to b is divisible by signalSpeed.
  • The path from c to b and the path from c to a do not share any edges.

Return an integer array count of length n where count[i] is the number of server pairs that are connectable through the server i.

 

Example 1:

Input: edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
Output: [0,4,6,6,4,0]
Explanation: Since signalSpeed is 1, count[c] is equal to the number of pairs of paths that start at c and do not share any edges.
In the case of the given path graph, count[c] is equal to the number of servers to the left of c multiplied by the servers to the right of c.

Example 2:

Input: edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3
Output: [2,0,0,0,0,0,2]
Explanation: Through server 0, there are 2 pairs of connectable servers: (4, 5) and (4, 6).
Through server 6, there are 2 pairs of connectable servers: (4, 5) and (0, 5).
It can be shown that no two servers are connectable through servers other than 0 and 6.

 

Constraints:

  • 2 <= n <= 1000
  • edges.length == n - 1
  • edges[i].length == 3
  • 0 <= ai, bi < n
  • edges[i] = [ai, bi, weighti]
  • 1 <= weighti <= 106
  • 1 <= signalSpeed <= 106
  • The input is generated such that edges represents a valid tree.

Approaches

2 approaches with complexity analysis and trade-offs.

This is a direct, brute-force approach. For each server in the network, we consider it as the central server c. Then, we examine every possible pair of other servers (a, b) to see if they are connectable through c.

Algorithm

  • Build an adjacency list from the edges array.
  • Initialize an answer array result of size n.
  • For each server c from 0 to n-1:
    • Perform a graph traversal (like BFS) starting from c to calculate distances and the first neighbor on the path to every other node. Store these in dist and firstHop arrays.
    • Initialize pairCount = 0.
    • Iterate a from 0 to n-1.
    • Iterate b from a + 1 to n-1.
    • If a == c or b == c, skip this pair.
    • Check if dist[a] % signalSpeed == 0, dist[b] % signalSpeed == 0, and firstHop[a] != firstHop[b].
    • If all true, increment pairCount.
    • Set result[c] = pairCount.
  • Return result.

Walkthrough

To check if a pair (a, b) is connectable through c, we must verify all four conditions given in the problem. The main computational tasks are finding the distances from c to a and b, and ensuring their paths from c are edge-disjoint.

A single traversal like Breadth-First Search (BFS) or Depth-First Search (DFS) starting from c can efficiently compute the distances to all other nodes in O(N) time. During this same traversal, we can also determine the "first hop" for each node, which is the neighbor of c on the unique path from c to that node. The path disjointness condition is met if and only if a and b have different first hops from c.

The overall algorithm is as follows:

  1. Build an adjacency list representation of the tree.
  2. For each server c from 0 to n-1: a. Run a traversal (e.g., BFS) from c to compute distances[i] and first_hops[i] for all other nodes i. b. Initialize a counter for connectable pairs to zero. c. Iterate through all pairs of servers (a, b) with a < b. d. If a or b is the same as c, skip. e. Check if distances[a] and distances[b] are divisible by signalSpeed, and if first_hops[a] is different from first_hops[b]. f. If all conditions hold, increment the pair counter. g. After checking all pairs, store the result for server c.
  3. Return the final counts.

Complexity

Time

O(N^3). The main loop runs `N` times. Inside, the traversal takes O(N). The nested loops to check all pairs `(a, b)` take O(N^2). Thus, the total complexity is O(N * (N + N^2)) = O(N^3), which is too slow for the given constraints.

Space

O(N) to store the adjacency list, a distance array, and a first-hop array for each central server.

Trade-offs

Pros

  • Conceptually simple and directly follows the problem definition.

Cons

  • The O(N^3) time complexity makes it infeasible for the given constraints.

Solutions

class Solution {private  int signalSpeed;private  List<int[]>[] g;public  int[] countPairsOfConnectableServers(int[][] edges, int signalSpeed) {    int n = edges.length + 1;    g = new List[n];    this.signalSpeed = signalSpeed;    Arrays.setAll(g, k->new ArrayList<>());    for (var e : edges) {      int a = e[0], b = e[1], w = e[2];      g[a].add(new int[]{b, w});      g[b].add(new int[]{a, w});    }    int[] ans = new int[n];    for (int a = 0; a < n; ++a) {      int s = 0;      for (var e : g[a]) {        int b = e[0], w = e[1];        int t = dfs(b, a, w);        ans[a] += s * t;        s += t;      }    }    return ans;  }private  int dfs(int a, int fa, int ws) {    int cnt = ws % signalSpeed == 0 ? 1 : 0;    for (var e : g[a]) {      int b = e[0], w = e[1];      if (b != fa) {        cnt += dfs(b, a, ws + w);      }    }    return cnt;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem