Find the City With the Smallest Number of Neighbors at a Threshold Distance — LeetCode 1334 Python Solution
MediumGraphDynamic ProgrammingShortest Path
- Problem
- #1334
- Pattern
- Depth-First Search
- Reading time
- 5 min
- Source
- leetcode.com
The problem
There are n cities numbered from 0 to n-1. Given the array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given the integer distanceThreshold.
Example
- Input
- n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
- Output
- 3
- Explanation
- The figure above describes the graph.
Python solution
Python
class Solution:
def findTheCity(
self, n: int, edges: List[List[int]], distanceThreshold: int
) -> int:
def dijkstra(u: int) -> int:
dist = [inf] * n
dist[u] = 0
vis = [False] * n
for _ in range(n):
k = -1
for j in range(n):
if not vis[j] and (k == -1 or dist[k] > dist[j]):
k = j
vis[k] = True
for j in range(n):
# dist[j] = min(dist[j], dist[k] + g[k][j])
if dist[k] + g[k][j] < dist[j]:
dist[j] = dist[k] + g[k][j]
return sum(d <= distanceThreshold for d in dist)
g = [[inf] * n for _ in range(n)]
for f, t, w in edges:
g[f][t] = g[t][f] = w
ans, cnt = n, inf
for i in range(n - 1, -1, -1):
if (t := dijkstra(i)) < cnt:
cnt, ans = t, i
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n·m) (typical) |
| Space | O(n·m) or optimized auxiliary |
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance is filed here because LeetCode tags it Graph, which is the vocabulary this hub collects.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
LeetCode 787Cheapest Flights Within K StopsMediumLeetCode 1786Number of Restricted Paths From First to Last NodeMediumLeetCode 1976Number of Ways to Arrive at DestinationMediumLeetCode 2977Minimum Cost to Convert String IIHardLeetCode 329Longest Increasing Path in a MatrixHardLeetCode 834Sum of Distances in TreeHard
Frequently asked questions
- How hard is LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance?
- LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance is rated Medium on LeetCode.
- What topics does LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance cover?
- LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance is tagged Graph, Dynamic Programming and Shortest Path on LeetCode.