LeetCode Problem 1334

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Graph Theory, Shortest Path

Solution

Edit

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

Problem Understanding

This problem gives us a weighted, undirected graph where each node represents a city and each edge represents a bidirectional road between two cities with a travel cost. We are also given a distanceThreshold, which acts as an upper limit on how far we are allowed to travel.

The goal is to determine which city can reach the fewest number of other cities such that the shortest path distance to those cities is less than or equal to distanceThreshold.

If multiple cities have the same minimum number of reachable neighbors, we must return the city with the largest city index.

In other words, for every city, we need to answer the following question:

"How many other cities can this city reach using the shortest possible routes, where the total distance does not exceed the threshold?"

Once we know that count for every city, we choose the city with the smallest count. If there is a tie, we choose the city with the larger index.

The input consists of:

• n, the number of cities labeled from 0 to n - 1
• edges, where each entry [u, v, w] means there is a bidirectional road between city u and city v with weight w
• distanceThreshold, the maximum allowed shortest path distance

The expected output is a single integer representing the selected city.

The constraints provide an important clue about which algorithm is appropriate. Since n <= 100, the graph is relatively small. Even an O(n³) solution is acceptable because:

[ 100^3 = 1,000,000 ]

One million operations is easily manageable in modern programming environments. This strongly suggests that an all-pairs shortest path algorithm such as Floyd-Warshall is a good fit.

There are several important edge cases to consider upfront.

The graph may not be fully connected, meaning some cities are unreachable from others. We must avoid counting unreachable cities.

Some cities may have zero reachable neighbors within the threshold. A naive implementation might accidentally count itself or mishandle infinite distances.

Multiple cities can have the same minimum reachable count, and the problem explicitly requires returning the city with the greatest index in this situation.

The problem guarantees that all edges are distinct and weights are positive, which means we do not need to handle duplicate edges or negative cycles.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to compute shortest paths from every city independently.

For each city, we could run a shortest path algorithm such as Dijkstra's algorithm to determine the shortest distance to every other city. Once we know these distances, we count how many cities are reachable within distanceThreshold.

After repeating this process for every city, we compare the counts and select the answer according to the tie-breaking rule.

This approach is correct because Dijkstra guarantees shortest path distances for graphs with positive weights, and edge weights in this problem are always positive.

However, repeatedly running shortest path computations introduces unnecessary repeated work. While still acceptable for the given constraints, it is not the cleanest solution when n is very small.

Key Insight for the Optimal Solution

The crucial observation is that we need the shortest distance between every pair of cities, not just from one source.

Because n <= 100, we can efficiently compute all-pairs shortest paths using the Floyd-Warshall algorithm.

Floyd-Warshall works by progressively allowing intermediate nodes in shortest paths. Initially, the only known distances are direct edges. Then, one city at a time is introduced as a possible intermediate stop between every pair of cities.

The transition is:

[ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) ]

This means:

• Either the current shortest path from i to j is already optimal
• Or going through city k produces a shorter route

After processing all intermediate cities, the matrix contains the shortest path distance between every pair.

Then we simply count how many cities each city can reach within the threshold and apply the tie-breaking rule.

Approach	Time Complexity	Space Complexity	Notes
Brute Force (Run Dijkstra from Every Node)	O(n × (E log n))	O(n + E)	Computes shortest paths separately for every city
Optimal (Floyd-Warshall)	O(n³)	O(n²)	Efficient for small n, directly computes all-pairs shortest paths

Algorithm Walkthrough

Optimal Algorithm, Floyd-Warshall

1. Initialize a distance matrix

Create an n × n matrix called dist.

Set every value to infinity because we initially assume cities are unreachable.

Set dist[i][i] = 0 for every city because the distance from a city to itself is always zero. 2. Populate direct edge distances

Iterate through edges.

For every road [u, v, weight], update:

dist[u][v] = weight
dist[v][u] = weight

Since the graph is undirected, we update both directions. 3. Run Floyd-Warshall

Use three nested loops.

The outer loop selects an intermediate city k.

For every pair (i, j), determine whether traveling through k gives a shorter path:

dist[i][j] = min(
    dist[i][j],
    dist[i][k] + dist[k][j]
)

This gradually improves all shortest path estimates. 4. Count reachable cities

For every city i, count how many cities j satisfy:

dist[i][j] <= distanceThreshold

Exclude the city itself. 5. Track the best city

Maintain:

• min_reachable, the smallest reachable count found so far
• result_city, the city index

If a city has a smaller count, update the answer.

If the count ties the current minimum, choose the larger city index.

Why it works

Floyd-Warshall guarantees that after processing intermediate city k, all shortest paths using only cities 0...k as intermediates are correct.

By the time every city has been processed as an intermediate node, the matrix contains the globally shortest distance between every pair of cities.

Since we count cities whose shortest path distance is within the threshold, and apply the required tie-breaking rule, the final result is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def findTheCity(
        self,
        n: int,
        edges: List[List[int]],
        distanceThreshold: int
    ) -> int:
        INF = float("inf")

        # Initialize distance matrix
        dist = [[INF] * n for _ in range(n)]

        # Distance to self is always 0
        for i in range(n):
            dist[i][i] = 0

        # Add direct edges
        for u, v, weight in edges:
            dist[u][v] = weight
            dist[v][u] = weight

        # Floyd-Warshall algorithm
        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]

        min_reachable = float("inf")
        result_city = -1

        # Count reachable cities
        for city in range(n):
            reachable_count = 0

            for neighbor in range(n):
                if (
                    city != neighbor
                    and dist[city][neighbor] <= distanceThreshold
                ):
                    reachable_count += 1

            # Tie-breaking favors larger city index
            if reachable_count <= min_reachable:
                min_reachable = reachable_count
                result_city = city

        return result_city

The implementation begins by creating a distance matrix initialized with infinity. Infinity represents cities that are currently unreachable.

The diagonal values are set to zero because every city has zero distance to itself.

Next, direct road information is inserted into the matrix. Since roads are bidirectional, both directions are updated.

The Floyd-Warshall phase uses three nested loops. The outermost loop picks an intermediate city k, while the inner loops examine every pair of cities (i, j). If traveling through k shortens the path, the matrix entry is updated.

Once shortest paths are complete, we iterate through each city and count how many cities fall within the threshold distance.

The tie-breaking logic is handled elegantly using:

if reachable_count <= min_reachable:

Using <= instead of < ensures that ties automatically favor the larger city index.

Go Solution

func findTheCity(n int, edges [][]int, distanceThreshold int) int {
	const INF = int(1e9)

	// Initialize distance matrix
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)

		for j := 0; j < n; j++ {
			if i == j {
				dist[i][j] = 0
			} else {
				dist[i][j] = INF
			}
		}
	}

	// Add direct edges
	for _, edge := range edges {
		u, v, weight := edge[0], edge[1], edge[2]
		dist[u][v] = weight
		dist[v][u] = weight
	}

	// Floyd-Warshall algorithm
	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if dist[i][k]+dist[k][j] < dist[i][j] {
					dist[i][j] =
						dist[i][k] + dist[k][j]
				}
			}
		}
	}

	minReachable := INF
	resultCity := -1

	// Count reachable cities
	for city := 0; city < n; city++ {
		reachableCount := 0

		for neighbor := 0; neighbor < n; neighbor++ {
			if city != neighbor &&
				dist[city][neighbor] <= distanceThreshold {
				reachableCount++
			}
		}

		// Tie-breaking favors larger index
		if reachableCount <= minReachable {
			minReachable = reachableCount
			resultCity = city
		}
	}

	return resultCity
}

The Go implementation follows the exact same logic as the Python version, but uses slices instead of nested lists.

Go does not have built-in infinity values for integers, so we define a sufficiently large constant (1e9) to represent unreachable distances.

Since edge weights and thresholds are bounded by 10^4, and n <= 100, integer overflow is not a concern with this sentinel value.

The tie-breaking logic remains identical by using <=, ensuring the larger city index is selected during ties.

Worked Examples

Example 1

Input

n = 4
edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
distanceThreshold = 4

Step 1: Initial Distance Matrix

From/To	0	1	2	3
0	0	3	∞	∞
1	3	0	1	4
2	∞	1	0	1
3	∞	4	1	0

Step 2: Floyd-Warshall Updates

After considering all intermediate cities:

From/To	0	1	2	3
0	0	3	4	5
1	3	0	1	2
2	4	1	0	1
3	5	2	1	0

Step 3: Count Reachable Cities

City	Reachable Cities	Count
0	1, 2	2
1	0, 2, 3	3
2	0, 1, 3	3
3	1, 2	2

Cities 0 and 3 both have the minimum count of 2.

Since ties favor the larger index, the answer is:

3

Example 2

Input

n = 5
edges = [
    [0,1,2],
    [0,4,8],
    [1,2,3],
    [1,4,2],
    [2,3,1],
    [3,4,1]
]
distanceThreshold = 2

Step 1: Final Shortest Path Matrix

From/To	0	1	2	3	4
0	0	2	5	5	4
1	2	0	3	3	2
2	5	3	0	1	2
3	5	3	1	0	1
4	4	2	2	1	0

Step 2: Count Reachable Cities

City	Reachable Cities	Count
0	1	1
1	0, 4	2
2	3, 4	2
3	2, 4	2
4	1, 2, 3	3

City 0 has the smallest reachable count.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n³)	Floyd-Warshall runs three nested loops over all cities
Space	O(n²)	The distance matrix stores shortest paths between every pair

The dominant cost comes from the Floyd-Warshall algorithm. Since we evaluate every triplet (i, j, k), the runtime is cubic.

Because n <= 100, this complexity is entirely reasonable. The matrix storage cost is quadratic because we maintain shortest distances between all city pairs.

Test Cases

sol = Solution()

# Example 1
assert (
    sol.findTheCity(
        4,
        [[0,1,3],[1,2,1],[1,3,4],[2,3,1]],
        4
    ) == 3
)  # tie-breaking with larger city index

# Example 2
assert (
    sol.findTheCity(
        5,
        [[0,1,2],[0,4,8],[1,2,3],
         [1,4,2],[2,3,1],[3,4,1]],
        2
    ) == 0
)  # provided example

# Minimum n
assert (
    sol.findTheCity(
        2,
        [[0,1,5]],
        4
    ) == 1
)  # no reachable neighbors, larger index wins

# Fully connected graph
assert (
    sol.findTheCity(
        3,
        [[0,1,1],[1,2,1],[0,2,1]],
        1
    ) == 2
)  # all cities equal, larger index wins

# Disconnected graph
assert (
    sol.findTheCity(
        4,
        [[0,1,2]],
        2
    ) == 3
)  # isolated cities

# Threshold too small
assert (
    sol.findTheCity(
        4,
        [[0,1,5],[1,2,5],[2,3,5]],
        1
    ) == 3
)  # nobody reachable

# Chain graph
assert (
    sol.findTheCity(
        5,
        [[0,1,2],[1,2,2],[2,3,2],[3,4,2]],
        2
    ) == 4
)  # endpoints have fewest neighbors

# Dense graph
assert (
    sol.findTheCity(
        4,
        [[0,1,1],[0,2,4],[0,3,7],
         [1,2,1],[1,3,3],[2,3,1]],
        4
    ) == 3
)  # shortest paths matter

Test	Why
Example 1	Verifies shortest path computation and tie-breaking
Example 2	Validates the second official example
Minimum n = 2	Tests smallest valid graph
Fully connected graph	Ensures equal counts choose larger index
Disconnected graph	Verifies unreachable cities are ignored
Threshold too small	Ensures zero reachable neighbors work correctly
Chain graph	Tests path accumulation
Dense graph	Verifies indirect shortest paths matter

Edge Cases

One important edge case occurs when multiple cities have the same minimum reachable count. This is easy to mishandle because many implementations naturally choose the first minimum encountered. The problem explicitly requires returning the city with the largest index. Our implementation handles this correctly by using:

if reachable_count <= min_reachable:

Using <= means ties overwrite previous answers, naturally favoring larger city indices.

Another edge case is disconnected graphs. Some cities may never be reachable from others because no path exists. If a solution incorrectly initializes distances or treats infinity improperly, unreachable cities might accidentally be counted. Our implementation avoids this by initializing unreachable paths to infinity and only counting distances that are less than or equal to distanceThreshold.

A third important edge case occurs when the threshold is extremely small. In some cases, a city may not be able to reach any other city. A buggy implementation might mistakenly count the city itself as reachable. We explicitly exclude self-counting using:

city != neighbor

This guarantees only distinct neighboring cities are counted.

A final edge case involves indirect paths being shorter than direct ones. For example, city A may connect directly to city C with cost 10, while A -> B -> C costs only 4. A naive implementation that only considers direct roads would fail. Floyd-Warshall guarantees that all indirect shortest paths are discovered and correctly incorporated into the final distances.