Find the City With the Smallest Number of Neighbors at a Threshold Distance

You are given n cities connected by weighted edges, and a distance threshold. Your job is to find the city that can reach the fewest other cities using paths whose total weight is at most the threshold. If multiple cities tie for the fewest reachable neighbors, return the one with the largest city number.

This is LeetCode 1334: Find the City With the Smallest Number of Neighbors at a Threshold Distance.

Why this problem matters

Most shortest-path problems on LeetCode ask you to find the distance between two specific nodes or from a single source to all others. This problem is different. You need shortest paths between every pair of cities, not just from one source. That makes it a natural fit for the Floyd-Warshall algorithm, which computes all-pairs shortest paths in a single pass.

Floyd-Warshall is one of those algorithms that looks deceptively simple. It is just three nested loops. But it solves a powerful problem: after it runs, you know the shortest distance between any two nodes in the graph. For problems where n is small (here, at most 100), the O(n^3) cost is perfectly acceptable.

Understanding when to reach for Floyd-Warshall versus Dijkstra is a useful skill. If you only need shortest paths from one source, Dijkstra is faster. If you need all pairs and the graph is small, Floyd-Warshall is simpler and avoids running Dijkstra n times.

The key insight

The problem breaks into two clean steps. First, compute the shortest path between every pair of cities using Floyd-Warshall. Second, for each city, count how many other cities are reachable within the threshold. The answer is the city with the smallest count, and if there is a tie, you pick the city with the largest id.

Floyd-Warshall works by considering each city k as a potential intermediate stop. For every pair (i, j), it checks whether routing through k produces a shorter path than the current best. After considering all possible intermediates, every entry in the distance matrix holds the true shortest path.

The solution

def findTheCity(n: int, edges: list[list[int]], distanceThreshold: int) -> int:
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        dist[i][i] = 0

    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    result = -1
    min_count = float('inf')

    for i in range(n):
        count = sum(1 for j in range(n) if i != j and dist[i][j] <= distanceThreshold)
        if count <= min_count:
            min_count = count
            result = i

    return result

The code starts by building a distance matrix initialized to infinity. Direct edges fill in their weights, and the diagonal is zero (every city has distance zero to itself). Then the three nested Floyd-Warshall loops run. Finally, you scan each row of the distance matrix and count how many entries fall within the threshold.

Notice the tie-breaking logic: the condition uses <= instead of < when comparing counts. Since you iterate cities from 0 to n-1, a later city with the same count naturally replaces an earlier one, giving you the largest id for free.

Visual walkthrough

The walkthrough shows the full pipeline. You start with the raw edge weights, run Floyd-Warshall to fill in all shortest paths, apply the threshold to see which cities are reachable from each node, and finally pick the city with the fewest connections. When cities 0 and 3 tie with two reachable neighbors each, the tie-break rule gives you city 3.

Complexity analysis

Time: The three nested loops over n cities give O(n^3). The final counting step is O(n^2), which is dominated by Floyd-Warshall. Since the constraint says n is at most 100, the worst case is about one million iterations, which runs in milliseconds.

Space: The n x n distance matrix takes O(n^2). No additional data structures are needed beyond the matrix itself.

The building blocks

1. Floyd-Warshall algorithm

Floyd-Warshall is a dynamic programming approach to all-pairs shortest paths. The key recurrence is: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) for each intermediate node k. The order of the loops matters. The outermost loop must iterate over k (the intermediate node), and the two inner loops iterate over all pairs (i, j). If you put k in an inner loop instead of the outermost, the algorithm produces incorrect results because it may use intermediate nodes before their shortest paths are finalized.

The algorithm works for graphs with negative edge weights too, as long as there are no negative cycles. If dist[i][i] becomes negative after running the algorithm, you know a negative cycle exists.

2. Threshold counting

After computing the distance matrix, the counting step is a simple scan of each row. For city i, you count how many entries dist[i][j] satisfy dist[i][j] <= distanceThreshold where j != i. The tie-breaking rule (return the largest id) is handled naturally by iterating forward and using <= in the comparison.

Edge cases

• No edges at all: Every city has zero reachable neighbors. All cities tie, so you return n - 1 (the largest id).
• All cities fully connected with tiny weights: Every city reaches every other city. All counts are n - 1. Return the largest id.
• Threshold of zero: No city can reach any other city (all edge weights are at least 1). Every city has zero reachable neighbors. Return n - 1.
• Single city: n = 1 with no edges. The only city is city 0, and it has zero reachable neighbors. Return 0.
• Two cities with one edge: If the edge weight is within the threshold, both cities have a count of 1. Tie-break gives city 1. If above the threshold, both have count 0, and you still return city 1.

From understanding to recall

You now understand how Floyd-Warshall fills in a distance matrix and how the counting step finds the answer. The algorithm is compact, just three nested loops followed by a scan. But writing it correctly under pressure means remembering that k must be the outermost loop, that the matrix needs proper initialization (infinity for non-edges, zero on the diagonal), and that the tie-break uses <= to favor larger ids.

Spaced repetition locks these details in. You practice initializing the matrix, writing the triple loop in the right order, and implementing the counting step. After a few sessions, the whole pattern flows naturally. When a shortest-path problem appears in your interview, you know immediately whether Floyd-Warshall or Dijkstra is the right tool, and you can write either one from memory.

Related posts

• Network Delay Time - Shortest paths in weighted graphs
• Cheapest Flights Within K Stops - Constrained shortest paths
• Number of Provinces - Graph connectivity

CodeBricks uses spaced repetition to help you internalize these graph patterns. Instead of solving hundreds of problems and forgetting them, you drill the core building blocks at intervals tuned to your memory. Floyd-Warshall, Dijkstra, BFS, and Union-Find all become tools you can reach for without hesitation.