#1334
Find the City With the Smallest Number of Neighbors at a Threshold Distance
MediumDynamic ProgrammingGraph TheoryShortest PathGraph TraversalDijkstra's AlgorithmPriority Queue
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n * (E + V log V)) |
| Space | O(n) | O(V) |
💡
Intuition
Time O(n * (E + V log V))Space O(V)
The optimal solution uses Dijkstra's algorithm to find the shortest paths from each city to all other cities. This is efficient for graphs with weighted edges and allows us to compute the reachable cities within the threshold quickly.
⚙️
Algorithm
4 steps- 1Step 1: Create a graph representation using an adjacency list from the edges.
- 2Step 2: For each city, run Dijkstra's algorithm to find the shortest distances to all other cities.
- 3Step 3: Count the number of cities reachable within the distanceThreshold for each city.
- 4Step 4: Track the city with the smallest number of reachable cities, and in case of a tie, select the city with the highest index.
solution.py31 lines
1import heapq
2from collections import defaultdict
3
4
5def findTheCity(n, edges, distanceThreshold):
6 graph = defaultdict(list)
7 for u, v, w in edges:
8 graph[u].append((v, w))
9 graph[v].append((u, w))
10
11 def dijkstra(start):
12 distances = [float('inf')] * n
13 distances[start] = 0
14 pq = [(0, start)] # (distance, node)
15 while pq:
16 current_dist, node = heapq.heappop(pq)
17 for neighbor, weight in graph[node]:
18 if current_dist + weight < distances[neighbor]:
19 distances[neighbor] = current_dist + weight
20 heapq.heappush(pq, (distances[neighbor], neighbor))
21 return distances
22
23 min_count = float('inf')
24 city_with_min_neighbors = -1
25 for city in range(n):
26 distances = dijkstra(city)
27 count = sum(1 for d in distances if d <= distanceThreshold)
28 if count < min_count or (count == min_count and city > city_with_min_neighbors):
29 min_count = count
30 city_with_min_neighbors = city
31 return city_with_min_neighborsℹ
Complexity note: The time complexity is O(n * (E + V log V)) because we run Dijkstra's algorithm for each city (n times), where E is the number of edges and V is the number of vertices. The space complexity is O(V) due to the storage of distances and the priority queue.
- 1Understanding graph traversal algorithms like BFS and Dijkstra is crucial for solving shortest path problems.
- 2When dealing with weighted graphs, Dijkstra's algorithm is often more efficient than BFS.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.