1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance (Floyd-Warshall)

Edited by Charles

Medium · Python · Graph

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

See the Python implementation and detailed notes below.

Original study notes follow, including intermediate snippets and earlier attempts.

Approach: Floyd-Warshall Algorithm

Core Idea

For each city, we need to know how many other cities can be reached with a shortest-path distance no greater than distanceThreshold.

Therefore, we need the shortest distance between every pair of cities.

This is an all-pairs shortest path problem, which can be solved directly using the Floyd-Warshall algorithm.

DP Definition

Define:

dp[i][j]

as:

The shortest distance from city i to city j.

Initially, create an n × n matrix:

dp = [[float('inf')] * n for _ in range(n)]

If two cities are not directly connected, their distance is initially:

∞

Initialization

Distance from a city to itself

The distance from every city to itself is 0:

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

So:

dp[0][0] = 0
dp[1][1] = 0
dp[2][2] = 0
...

Add the edges

For every edge:

[u, v, w]

cities u and v are connected with distance w.

Since the graph is undirected:

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

We must update both directions.

Floyd-Warshall

The core idea of Floyd-Warshall is:

For every pair of cities i and j, check whether going through another city k gives a shorter path.

Originally:

i --------------------> j

We try:

i --------> k --------> j

Therefore:

new distance = dp[i][k] + dp[k][j]

If this is shorter than the current:

dp[i][j]

we update it.

The transition is:

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

Why Is k the Outer Loop?

The Floyd-Warshall loop must be:

for k in range(n):
    for i in range(n):
        for j in range(n):

Here, k represents the intermediate city that we are currently allowing in our shortest paths.

Conceptually:

k = 0
→ allow city 0 as an intermediate city

k = 1
→ allow cities 0, 1 as intermediate cities

k = 2
→ allow cities 0, 1, 2 as intermediate cities

...

k = n - 1
→ allow all cities as intermediate cities

After processing all values of k, dp[i][j] contains the shortest distance between every pair of cities.

Original 3D DP Interpretation

Floyd-Warshall can originally be understood as a 3D DP.

Define:

DP[k][i][j]

as:

The shortest distance from i to j when only the first k cities are allowed to be intermediate nodes.

For each intermediate node k, there are two possibilities.

Case 1: Do not use k

i ----------------> j

Keep the previous shortest distance.

Case 2: Use k

i ------> k ------> j

The distance becomes:

distance(i, k) + distance(k, j)

Therefore, conceptually:

DP[k][i][j]
=
min(
    previous distance from i to j,
    distance from i to k + distance from k to j
)

Because each stage only depends on the previous stage, the k dimension can be optimized away.

This gives the standard 2D Floyd-Warshall transition:

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

So the 2D matrix is a space-optimized version of the original 3D DP.

Count Reachable Cities

After Floyd-Warshall finishes, dp[i][j] is the shortest distance from city i to city j.

For each city i:

count = 0

we check every other city j:

if i != j and dp[i][j] <= distanceThreshold:
    count += 1

The condition:

i != j

is necessary because we should not count the city itself.

The condition:

dp[i][j] <= distanceThreshold

means city j is reachable from city i within the required threshold.

Find the City with the Minimum Count

We maintain:

minCount = float('inf')
res = -1

For every city:

if count <= minCount:
    minCount = count
    res = i

Why <= Instead of <?

This is important.

The problem says:

If multiple cities have the same minimum number of reachable cities, return the city with the greatest number.

We iterate through cities in increasing order:

0 → 1 → 2 → ... → n - 1

Suppose:

city 2 → count = 3
city 4 → count = 3

When processing city 4:

count <= minCount

is still True.

Therefore:

res = 4

replaces:

res = 2

This automatically keeps the largest city number when there is a tie.

Example

Suppose:

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

distanceThreshold = 4

Initially, we only know direct distances:

      0    1    2    3

0     0    3    ∞    ∞
1     3    0    1    4
2     ∞    1    0    1
3     ∞    4    1    0

Floyd-Warshall discovers shorter indirect paths.

For example:

0 → 1 → 2

has distance:

3 + 1 = 4

so:

dp[0][2] = 4

Similarly:

0 → 1 → 2 → 3

has distance:

3 + 1 + 1 = 5

After Floyd-Warshall finishes, every dp[i][j] represents the shortest distance between i and j.

Then we count how many cities are within distanceThreshold for each city and select the city with the smallest count.

Complexity

Floyd-Warshall uses three nested loops:

for k in range(n):
    for i in range(n):
        for j in range(n):

Therefore:

Time Complexity: O(n³)

The distance matrix contains n × n values:

Space Complexity: O(n²)

Key Takeaways

Floyd-Warshall is for all-pairs shortest paths

Use Floyd-Warshall when we need:

shortest distance between every pair of nodes

rather than only the shortest paths from one source.

Core transition

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

Meaning:

Do not go through k:
i ----------------> j

Go through k:
i ------> k ------> j

Take the shorter one.

Loop order

Always remember:

for k in range(n):
    for i in range(n):
        for j in range(n):

k must be the outer loop because it represents the DP stage: which intermediate nodes are currently allowed.

Floyd-Warshall is originally a 3D DP

Conceptually:

DP[k][i][j]

represents the shortest path from i to j when only certain nodes are allowed as intermediate nodes.

The standard implementation compresses this into:

dp[i][j]

so the space complexity decreases from:

O(n³) → O(n²)

Tie-breaking in LeetCode 1334

Because the problem asks for the largest city number when counts are equal:

if count <= minCount:

rather than:

if count < minCount:

This allows a later, larger city index to replace an earlier one when their reachable-city counts are equal.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 3, 2026

Python solution

class Solution:
    def findTheCity(
        self,
        n: int,
        edges: List[List[int]],
        distanceThreshold: int
    ) -> int:

        dp = [[float('inf')] * n for _ in range(n)]

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

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

        # Floyd-Warshall
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dp[i][j] = min(
                        dp[i][k] + dp[k][j],
                        dp[i][j]
                    )

        minCount, res = float('inf'), -1

        for i in range(n):
            count = 0

            for j in range(n):
                if i != j and dp[i][j] <= distanceThreshold:
                    count += 1

            if count <= minCount:
                minCount = count
                res = i

        return res

---

Back to Day 55 Graph XIII · All Algorithm notes