#3243
Shortest Distance After Road Addition Queries I
MediumArrayBreadth-First SearchGraph TheoryGraph TraversalBreadth-First Search
Approaches
Brute ForceOptimal
Complexity Comparison
| Brute Force | Optimal Solution★ | |
|---|---|---|
| Time | O(n²) | O(n) |
| Space | O(n) | O(n) |
💡
Intuition
Time O(n)Space O(n)
The optimal approach uses a graph representation and a modified BFS or Dijkstra's algorithm to efficiently find the shortest path after each query. Instead of recalculating the entire path, we only update the graph and check the shortest path incrementally.
⚙️
Algorithm
3 steps- 1Step 1: Initialize a graph with n cities and unidirectional roads from city i to city i + 1.
- 2Step 2: For each query, add the new road from u to v.
- 3Step 3: Use BFS or Dijkstra's algorithm to find the shortest path from city 0 to city n-1 after each query.
solution.py26 lines
1from collections import deque
2
3
4def shortest_distance_optimal(n, queries):
5 graph = {i: [i + 1] for i in range(n - 1)}
6 graph[n - 1] = []
7 results = []
8
9 for u, v in queries:
10 graph[u].append(v)
11 results.append(bfs(graph, n))
12 return results
13
14
15def bfs(graph, n):
16 queue = deque([(0, 0)]) # (current city, distance)
17 visited = set()
18 while queue:
19 city, dist = queue.popleft()
20 if city == n - 1:
21 return dist
22 for neighbor in graph[city]:
23 if neighbor not in visited:
24 visited.add(neighbor)
25 queue.append((neighbor, dist + 1))
26 return -1 # If no path foundℹ
Complexity note: The time complexity is O(n) for each query due to the BFS, leading to O(q * n) overall. This is efficient given the constraints.
- 1Graph representation is crucial for understanding city connections.
- 2BFS is effective for finding shortest paths in unweighted graphs.
Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.