Abstract / Summary

Count pairs of servers that can connect through paths with total weight not exceeding a given limit.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 56% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Depth First Search
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The countPairsOfConnectableServers method receives a list of weighted edges describing an undirected graph and an integer signalSpeed. For each node it computes how many unordered pairs of distinct servers can exchange a signal whose total travel time is a multiple of signalSpeed. The result is produced as a generator that yields one integer per node, representing the number of such pairs that are reachable from that node.

Graph Construction

The first step determines the highest node identifier to allocate a fixed-size adjacency list. An empty list is created for each possible node index, then each edge is unpacked into its two endpoints and weight. Both directions are stored, yielding a symmetric representation suitable for depth-first traversal.

size = max(max(a, b) for a, b, weight in edges) + 1
next = [ [] for _ in range(size) ]
for a, b, weight in edges:
    next[a].append((b, weight))
    next[b].append((a, weight))

Recursive Depth-First Search with Modulo Distance

A cached helper deeper performs a DFS from a given node, tracking the cumulative distance modulo signalSpeed. The base case treats a distance of zero as a “connectable” server, contributing one to the count. For each neighbor that is not the immediate parent, the function recurses, passing the updated modulo distance. The @cache decorator memoizes results for a specific (node, parent, distance) triple, preventing repeated exploration of identical sub-trees.

@cache
def deeper(node, parent, distance):
    connectable = 1 if distance == 0 else 0
    for other, weight in next[node]:
        if other != parent:
            connectable += deeper(other, node, (distance + weight) % signalSpeed)
    return connectable

Counting Connectable Servers per Node

The outer loop iterates over every node index. For each neighbor of the current node, deeper is invoked once, producing the number of servers reachable through that neighbor whose path length is a multiple of signalSpeed. These counts are stored in a temporary list good. The total number of unordered pairs is then derived by a two-phase accumulation: first the sum of all good values, then a pairwise multiplication that subtracts each entry from the running total before forming the product. This technique avoids a quadratic nested loop while still accounting for every distinct pair.

for node in range(size):
    good = []
    for other, weight in next[node]:
        good.append(deeper(other, node, weight % signalSpeed))

    total = sum(good)
    combinations = 0
    for g in good:
        total        -= g
        combinations += g * total

    yield combinations

Edge Cases Handled

When a node has no incident edges, the adjacency list entry is empty; the inner loop over neighbors produces an empty good list, resulting in a yielded value of zero, correctly indicating that no pairs exist. The modulo operation (distance + weight) % signalSpeed naturally wraps distances that exceed signalSpeed, ensuring that any path whose total length is an exact multiple of the signal speed is recognized as having a zero remainder. The base case distance == 0 captures the situation where the cumulative distance from the start node to a descendant node is already a multiple of signalSpeed, even if the path consists of a single edge whose weight itself is a multiple of signalSpeed. Because the recursion excludes the immediate parent, cycles are prevented in an undirected graph, guaranteeing termination even in the presence of self-loops or multiple edges.

Performance Optimizations

Memoization via @cache eliminates redundant traversals of identical sub-trees, turning what would be an exponential exploration into a linear pass relative to the number of distinct (node, parent, distance) states. By passing the parent identifier, the algorithm avoids revisiting the edge it just came from, thereby preventing unnecessary backtracking without needing an explicit visited set for each DFS call. The combination counting avoids a double nested iteration over the good list; instead it maintains a running total and computes each pair contribution in constant time per neighbor, yielding an overall linear cost per node with respect to its degree. The use of a pre-allocated adjacency list (next) provides O(1) access to neighbor collections, and the modulo operation is performed only when necessary, keeping arithmetic overhead minimal.

Imagine a big map with many islands connected by bridges. Some bridges are long and some are short. Every time you cross a bridge, you send a tiny signal that travels along the path. These signals are special because they only work if the total distance they travel can be divided perfectly by a certain number. If the distance works out exactly, the signal reaches its home base.

The computer starts by looking at the whole map to see how everything fits together. It turns the list of bridges into a drawing where it knows exactly which island connects to which.

When the computer picks a starting island, it sends out explorers along every bridge connected to that spot. Each explorer travels through the network, constantly adding up the distance they have covered. Every time they reach a new island, they check if their current distance matches the rule about being divisible. If they find a spot where the rule works, they mark it down.

After the explorers check all the paths branching out from the starting island, the computer compares the results from different directions. It looks to see how many signals from one set of bridges can team up with signals from another set of bridges to make a pair. By multiplying these numbers together, the computer figures out exactly how many pairs of islands can talk to each other while following the rules of the signals. The computer does this for every single island on the map until it has a complete list of all the possible pairs.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	fsq			C++
	JoshCrozier	JS
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality