Abstract / Summary

Given a list of city distances, find the city with the fewest cities within a certain distance threshold.

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 73% (400k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming
• Graph Theory
• Shortest Path

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 provided implementation solves the problem of finding the city that has the smallest number of reachable neighboring cities within a given distance threshold. It builds a complete distance matrix for all city pairs, applies a modified Floyd-Warshall algorithm to compute shortest paths, and finally selects the city with the minimal count of reachable neighbors, breaking ties by choosing the city with the larger index.

Initialization of the distance matrix

The algorithm begins by defining a very large sentinel value (unknown) that represents the absence of a direct connection between two cities. A two-dimensional list all of size n × n is created, each entry initialized to this sentinel. This matrix will later hold the shortest distances between every pair of cities.

unknown = 10**10
all = [ [ unknown ] * n for _ in range(n) ]

Self-loops are explicitly set to zero, reflecting that the distance from a city to itself is always zero.

for a in range(n):
    all[a][a] = 0

Populating direct edge weights

The input list edges contains triples (a, b, weight) describing an undirected road between cities a and b. For each edge the matrix entries for both directions are updated with the given weight, overwriting the sentinel value.

for a, b, weight in edges:
    all[a][b] = weight
    all[b][a] = weight

Modified Floyd-Warshall computation

The core of the solution is a triple-nested loop that iteratively improves the distance estimates using an intermediate city mid. The outermost loop iterates over each possible intermediate city. The inner loops consider pairs (a, b) where a is distinct from mid and b is strictly greater than a. By restricting b to a + 1 onward, the algorithm processes each unordered pair only once and mirrors the result to the symmetric entry, halving the number of updates compared with a naïve full matrix scan.

for mid in range(n):
    for a in range(n):
        if a != mid and all[a][mid] < unknown:
            for b in range(a + 1, n):
                all[a][b] = all[b][a] = min(all[a][b], all[a][mid] + all[mid][b])

The condition all[a][mid] < unknown ensures that only reachable intermediate paths are considered, thereby skipping unnecessary additions involving the sentinel value. This check prevents overflow and reduces the number of arithmetic operations.

Counting reachable neighbors per city

After the distance matrix contains the shortest paths, the algorithm iterates over each row to count how many cities are reachable within the distanceThreshold. The comparison r <= distanceThreshold includes the city itself because its distance to itself is zero, which aligns with the problem definition that counts the city as reachable.

result = 0
low    = n
for i, row in enumerate(all):
    nearby = sum(1 for r in row if r <= distanceThreshold)
    if low >= nearby:
        low = nearby
        result = i

The variables low and result keep track of the smallest neighbor count observed so far and the corresponding city index. The condition low >= nearby implements the tie-breaking rule: when two cities have the same count, the later city (higher index) replaces the earlier one, because the comparison uses >= rather than >.

Edge cases handled by the implementation

The code gracefully handles the situation where the graph is disconnected. In such cases, pairs of cities that have no connecting path retain the sentinel value unknown, which is larger than any realistic distance threshold, so they are never counted as reachable. The explicit check all[a][mid] < unknown prevents attempts to combine an unreachable segment with another distance, thereby avoiding incorrect path reductions.

When the input contains a single city (n == 1), the matrix is a 1×1 array with a zero entry. The neighbor count for that city becomes one (the city itself), and the algorithm correctly returns index 0 as the result.

If multiple edges between the same pair of cities are provided, the later assignment overwrites earlier ones. Since the algorithm only needs the smallest direct weight, the final matrix entry will reflect the last edge processed; however, the Floyd-Warshall phase will still discover any shorter indirect routes, ensuring correctness.

Performance optimizations observed

The most notable optimization is the reduction of symmetric updates by iterating b from a + 1 onward and mirroring the computed minimum to both [a][b] and [b][a]. This halves the number of inner-loop iterations compared with a full double loop over all (a, b) pairs.

Another optimization is the early exit condition all[a][mid] < unknown. By skipping the inner addition when the intermediate distance is still unknown, the algorithm avoids unnecessary arithmetic and the creation of large intermediate sums that would be discarded anyway.

The use of a sentinel value that is far larger than any possible path length ensures that the min operation never mistakenly selects an unreachable path, while still allowing simple integer arithmetic without special case handling.

Finally, the neighbor counting step employs a generator expression inside sum, which iterates over each row only once and avoids constructing intermediate lists, keeping memory usage minimal during that phase.

Imagine looking at a map of many little towns connected by roads. Each road has a length, and some are short while others are long. This code helps figure out which town is the best one to live in if you want to be close to as many other towns as possible without traveling too far.

First, the code creates a giant grid that acts like a notepad to keep track of how long it takes to get from one town to every other town. It starts by saying every town is very far away from the others, except for when you are already in the town you started at, which takes zero effort. Then, it goes through all the roads on the map and writes down how long each one takes to cross.

Next, the code starts a smart trick to find shortcuts. It looks at every town and asks if going through that middle point makes the trip to another town shorter. If it finds a shortcut, it updates the map so the travel time is as small as possible. It does this over and over until every possible trip has the shortest route found.

After all the shortcuts are discovered, the code looks at each town again. It counts how many other towns can be reached within a certain distance limit. A town that has the smallest number of neighbors within that distance is chosen as the winner. This process ensures that the focus stays on finding the most central or well-connected place based on the rules provided.

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	C++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++	JS	Java		Go	Python	TS
	MemoryLimitExceeded	C++					Python
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	JoshCrozier		JS
	lzl124631x	C++
	suxrobGM				C#
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
JoshCrozier	JavaScript
lzl124631x	C++
suxrobGM	C#
varunu28	Java
wisdompeak	C++

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