NeetCode #600LC-3243MediumGraphs
← Back to All Problems#600 · #3243 · Shortest Distance After Road Addition Queries I(新增道路查询后的最短距离 I)
📌 Problem Statement & Constraints
There are
n cities numbered 0..n-1 with a directed road from i to i+1 for each i. For each query [u, v], add a road u -> v and return the shortest path length from 0 to n-1. Constraints: 1 <= n <= 500, 1 <= queries.length <= 500, 0 <= u < v < n.💡 Core Algorithmic Approaches
- Roads only go forward, so a BFS from 0 gives the shortest distance.
- After each query, re-run the BFS over the updated adjacency list.
- With
n, q <= 500this is at most500 * (500 + 500)operations -- comfortably fast. - For much larger inputs, a more clever incremental structure would be needed.
💻 Benchmark Python3 Implementation
class Solution:
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
from collections import deque
adj = [[] for _ in range(n)]
for i in range(n - 1):
adj[i].append(i + 1) # the initial chain
def bfs() -> int:
dist = [-1] * n
dist[0] = 0
q = deque([0])
while q:
node = q.popleft()
if node == n - 1:
return dist[node]
for nxt in adj[node]:
if dist[nxt] == -1:
dist[nxt] = dist[node] + 1
q.append(nxt)
return dist[n - 1]
res = []
for u, v in queries:
adj[u].append(v) # add the new road
res.append(bfs())
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(q * (V + E)): one BFS per query.
💾 Space Complexity
O(V + E) for the adjacency list.
⚠️ Interview Pitfalls & Follow-ups
- Assuming the graph stays a simple chain: the added roads create shortcuts.
- Forgetting the initial chain: without it, only the added roads exist.
- Using a DFS: it does not guarantee the shortest path.
- Caching the previous answer: a new road can only shorten the distance, but the recomputation is still needed to know by how much.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.