# Shortest Distance After Road Addition Queries I **Difficulty:** MEDIUM [External](https://leetcode.com/problems/shortest-distance-after-road-addition-queries-i) Canonical: https://scaleengineer.com/dsa/problems/shortest-distance-after-road-addition-queries-i **Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** Array, Graph --- ## Problem You are given an integer `n` and a 2D integer array `queries`. There are `n` cities numbered from `0` to `n - 1`. Initially, there is a **unidirectional** road from city `i` to city `i + 1` for all `0 <= i < n - 1`. `queries[i] = [ui, vi]` represents the addition of a new **unidirectional** road from city `ui` to city `vi`. After each query, you need to find the **length** of the **shortest path** from city `0` to city `n - 1`. Return an array `answer` where for each `i` in the range `[0, queries.length - 1]`, `answer[i]` is the _length of the shortest path_ from city `0` to city `n - 1` after processing the **first** `i + 1` queries. **Example 1:** **Input:** n = 5, queries = \[\[2,4\],\[0,2\],\[0,4\]\] **Output:** \[3,2,1\] **Explanation:** ![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-i/image0.jpg) After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3. ![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-i/image1.jpg) After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2. ![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-i/image2.jpg) After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1. **Example 2:** **Input:** n = 4, queries = \[\[0,3\],\[0,2\]\] **Output:** \[1,1\] **Explanation:** ![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-i/image3.jpg) After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1. ![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-i/image4.jpg) After the addition of the road from 0 to 2, the length of the shortest path remains 1. **Constraints:** * `3 <= n <= 500` * `1 <= queries.length <= 500` * `queries[i].length == 2` * `0 <= queries[i][0] < queries[i][1] < n` * `1 < queries[i][1] - queries[i][0]` * There are no repeated roads among the queries. # Approaches ## Brute Force with Floyd-Warshall This approach recalculates the shortest paths between all pairs of cities after each query using the Floyd-Warshall algorithm. While it correctly finds the shortest path from city 0 to city n-1, it's highly inefficient because it computes much more information than required. **Time:** O(Q * n^3), where `Q` is the number of queries and `n` is the number of cities. For each of the `Q` queries, we run Floyd-Warshall which takes `O(n^3)` time. · **Space:** O(n^2) to store the distance matrix for each query. **Pros:** Conceptually simple if one is familiar with the Floyd-Warshall algorithm. **Cons:** Extremely inefficient due to its high time complexity.; Recomputes all-pairs shortest paths from scratch for every query, which is massive overkill for this problem.; Will result in a 'Time Limit Exceeded' error for the given constraints. ### Explanation The Floyd-Warshall algorithm is a dynamic programming approach to find the shortest paths between all pairs of vertices in a weighted directed graph. For each query, we construct a distance matrix representing the graph at that stage. The algorithm works as follows: 1. Initialize an `n x n` distance matrix `dist`. `dist[i][j]` is 1 if there's a direct road from `i` to `j`, `0` if `i == j`, and infinity otherwise. 2. The initial roads `i -> i+1` are added to the matrix. 3. For the `k`-th query, all roads from `queries[0]` to `queries[k]` are added. 4. The Floyd-Warshall algorithm is then run on this matrix. It iterates through all possible intermediate vertices `k` for each pair of source `i` and destination `j`, and updates the shortest path `dist[i][j]` if the path through `k` is shorter. 5. After the algorithm completes, `dist[0][n-1]` contains the length of the shortest path from city 0 to city n-1. This process is repeated for every single query. ```java class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { int[] answer = new int[queries.length]; java.util.List currentEdges = new java.util.ArrayList<>(); for (int i = 0; i < queries.length; i++) { currentEdges.add(queries[i]); long[][] dist = new long[n][n]; for (int r = 0; r < n; r++) { java.util.Arrays.fill(dist[r], Integer.MAX_VALUE); dist[r][r] = 0; } // Add initial edges for (int j = 0; j < n - 1; j++) { dist[j][j + 1] = 1; } // Add query edges for (int[] edge : currentEdges) { dist[edge[0]][edge[1]] = 1; } // Floyd-Warshall algorithm for (int k = 0; k < n; k++) { for (int u = 0; u < n; u++) { for (int v = 0; v < n; v++) { if (dist[u][k] != Integer.MAX_VALUE && dist[k][v] != Integer.MAX_VALUE) { dist[u][v] = Math.min(dist[u][v], dist[u][k] + dist[k][v]); } } } } answer[i] = (int) dist[0][n - 1]; } return answer; } } ``` ### Algorithm - For each query `i` from `0` to `queries.length - 1`: 1. Create an `n x n` distance matrix `dist`, initialized with infinity, except for `dist[j][j] = 0`. 2. Populate `dist` with initial edges: `dist[j][j+1] = 1` for `0 <= j < n-1`. 3. Populate `dist` with query edges from `0` to `i`: `dist[u][v] = 1` for each query `[u, v]`. 4. Apply the Floyd-Warshall algorithm to compute all-pairs shortest paths. 5. Store `dist[0][n-1]` as the answer for query `i`. ## Re-compute with Breadth-First Search (BFS) A more optimized approach is to model the problem as a single-source shortest path problem on an unweighted graph. For each query, we add the new road to our graph representation and then run a Breadth-First Search (BFS) from city 0 to find the shortest path to city n-1. **Time:** O(Q * (n + E_i)), where `E_i` is the number of edges after `i` queries. `E_i = (n-1) + (i+1)`. This simplifies to `sum_{i=0}^{Q-1} O(n+i) = O(Q*n + Q^2)`. This is efficient enough for the given constraints. · **Space:** O(n + Q) to store the adjacency list, which grows with each query. The BFS also requires `O(n)` space for the queue and distance array. **Pros:** Much more efficient than Floyd-Warshall.; Correctly solves the problem within the time limits.; Relatively straightforward to implement. **Cons:** Still involves re-computing the shortest path from scratch after each query, even if the new road doesn't affect the shortest path. ### Explanation Since all roads have a length of 1, the problem is equivalent to finding the shortest path in an unweighted graph. BFS is the standard algorithm for this. We maintain a graph, represented by an adjacency list. The process for each query is: 1. Start with a graph containing the initial roads `i -> i+1`. 2. For each query `[u, v]`, add the new directed edge `u -> v` to the adjacency list. 3. After adding the edge, perform a BFS starting from the source city, 0. 4. BFS explores the graph layer by layer, guaranteeing that we find the shortest path to all reachable cities. 5. During the BFS, we keep track of distances in a `dist` array. `dist[j]` stores the shortest distance from city 0 to city `j`. 6. The BFS terminates once we have explored all reachable nodes. The answer for the current query is `dist[n-1]`. This is better than Floyd-Warshall because BFS (`O(V+E)`) is much faster than `O(V^3)`. We avoid re-building the graph from scratch by incrementally adding edges. ```java class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { int[] answer = new int[queries.length]; java.util.List> adj = new java.util.ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new java.util.ArrayList<>()); } // Add initial edges for (int i = 0; i < n - 1; i++) { adj.get(i).add(i + 1); } for (int i = 0; i < queries.length; i++) { int u = queries[i][0]; int v = queries[i][1]; adj.get(u).add(v); // Run BFS to find shortest path from 0 to n-1 answer[i] = bfs(n, adj); } return answer; } private int bfs(int n, java.util.List> adj) { int[] dist = new int[n]; java.util.Arrays.fill(dist, -1); java.util.Queue q = new java.util.LinkedList<>(); dist[0] = 0; q.offer(0); while (!q.isEmpty()) { int curr = q.poll(); if (curr == n - 1) { return dist[curr]; } for (int neighbor : adj.get(curr)) { if (dist[neighbor] == -1) { dist[neighbor] = dist[curr] + 1; q.offer(neighbor); } } } return -1; // Should not be reached } } ``` ### Algorithm 1. Initialize an adjacency list `adj` for `n` cities. 2. Add the initial roads `i -> i+1` to `adj`. 3. For each query `i` from `0` to `queries.length - 1`: a. Add the new road `queries[i][0] -> queries[i][1]` to `adj`. b. Perform a BFS starting from city 0. i. Use a queue and a `distance` array, initialized to -1 (or infinity). ii. `distance[0] = 0`, push 0 to the queue. iii. While the queue is not empty, dequeue a city `u`, and for each neighbor `v`, if `v` is unvisited, update its distance and enqueue it. c. The shortest path length is `distance[n-1]`. Store it in the answer array. ## Incremental Shortest Path Updates This is the most optimized approach. Instead of re-computing everything, we maintain the shortest distances from city 0 to all other cities (`d0`) and from all cities to city n-1 (`dn`). When a new road `u -> v` is added, we can quickly check if it creates a new shortcut. Then, we only update the distances for the parts of the graph that are actually affected by this new road. **Time:** O(Q * (n + E_i)) in the worst case, which is `O(Q*n + Q^2)`. This happens if every update requires traversing the entire graph. However, on average, the updates are localized, making it faster than the simple BFS approach in practice. · **Space:** O(n + Q) for the adjacency lists. `O(n)` for the distance arrays and propagation queues. **Pros:** Most efficient approach, especially on average.; Avoids redundant computations by only updating affected path lengths. **Cons:** More complex to implement correctly compared to the simple BFS approach.; Worst-case time complexity is the same as the simple BFS approach. ### Explanation We maintain two distance arrays: - `d0[i]`: shortest distance from city 0 to city `i`. - `dn[i]`: shortest distance from city `i` to city `n-1`. Initially, with only roads `i -> i+1`, `d0[i] = i` and `dn[i] = (n-1) - i`. For each query `(u, v)`: 1. The new road `u -> v` might create shorter paths. We must update our `d0` and `dn` arrays to reflect this for future queries. 2. **Updating `d0`**: The new road provides a new path to `v` of length `d0[u] + 1`. If this is shorter than the current `d0[v]`, we update `d0[v]` and propagate this change to all cities reachable from `v`. This propagation can be done with a BFS-like procedure starting from `v`. 3. **Updating `dn`**: Similarly, the new road provides a new path from `u` to `n-1` (via `v`) of length `1 + dn[v]`. If this is shorter than `dn[u]`, we update `dn[u]` and propagate this change backward to all cities that can reach `u`. This is done with a BFS-like procedure on the graph with reversed edges, starting from `u`. 4. After the updates, `d0[n-1]` will hold the true shortest path length from 0 to `n-1`. This approach is efficient because the propagation updates only run if a distance is actually improved, and they may only traverse a small portion of the graph. ```java class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { int[] answer = new int[queries.length]; java.util.List> adj = new java.util.ArrayList<>(); java.util.List> revAdj = new java.util.ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new java.util.ArrayList<>()); revAdj.add(new java.util.ArrayList<>()); } int[] d0 = new int[n]; int[] dn = new int[n]; for (int i = 0; i < n; i++) { d0[i] = i; dn[i] = n - 1 - i; if (i < n - 1) { adj.get(i).add(i + 1); revAdj.get(i + 1).add(i); } } for (int i = 0; i < queries.length; i++) { int u = queries[i][0]; int v = queries[i][1]; adj.get(u).add(v); revAdj.get(v).add(u); // Update d0 (distances from 0) if (d0[u] + 1 < d0[v]) { d0[v] = d0[u] + 1; java.util.Queue q = new java.util.LinkedList<>(); q.offer(v); while (!q.isEmpty()) { int curr = q.poll(); for (int neighbor : adj.get(curr)) { if (d0[curr] + 1 < d0[neighbor]) { d0[neighbor] = d0[curr] + 1; q.offer(neighbor); } } } } // Update dn (distances to n-1) if (dn[v] + 1 < dn[u]) { dn[u] = dn[v] + 1; java.util.Queue q = new java.util.LinkedList<>(); q.offer(u); while (!q.isEmpty()) { int curr = q.poll(); for (int neighbor : revAdj.get(curr)) { if (dn[curr] + 1 < dn[neighbor]) { dn[neighbor] = dn[curr] + 1; q.offer(neighbor); } } } } answer[i] = d0[n-1]; } return answer; } } ``` ### Algorithm 1. Initialize `d0[i] = i` and `dn[i] = n-1-i`. 2. Initialize `adj` and `revAdj` lists with the initial `i -> i+1` roads. 3. For each query `(u, v)`: a. Add edge `u -> v` to `adj` and `v -> u` to `revAdj`. b. Check if `d0[u] + 1 < d0[v]`. If so, update `d0[v]` and start a BFS-like propagation from `v` using `adj` to update `d0` for successors. c. Check if `dn[v] + 1 < dn[u]`. If so, update `dn[u]` and start a BFS-like propagation from `u` using `revAdj` to update `dn` for predecessors. d. The answer for the current query is the updated `d0[n-1]`. # Solutions ### Java ```java class Solution { private List[] g; private int n; public int[] shortestDistanceAfterQueries(int n, int[][] queries) { this.n = n; g = new List[n]; Arrays.setAll(g, i->new ArrayList<>()); for (int i = 0; i < n - 1; ++i) { g[i].add(i + 1); } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int u = queries[i][0], v = queries[i][1]; g[u].add(v); ans[i] = bfs(0); } return ans; } private int bfs(int i) { Deque q = new ArrayDeque<>(); q.offer(i); boolean[] vis = new boolean[n]; vis[i] = true; for (int d = 0;; ++d) { for (int k = q.size(); k > 0; --k) { int u = q.poll(); if (u == n - 1) { return d; } for (int v : g[u]) { if (!vis[v]) { vis[v] = true; q.offer(v); } } } } } } ``` ### CPP ```cpp class Solution { public: vector shortestDistanceAfterQueries(int n, vector> &queries) { vector g[n]; for (int i = 0; i < n - 1; ++i) { g[i].push_back(i + 1); } auto bfs = [&](int i) -> int { queue q{{i}}; vector vis(n); vis[i] = true; for (int d = 0;; ++d) { for (int k = q.size(); k; --k) { int u = q.front(); q.pop(); if (u == n - 1) { return d; } for (int v : g[u]) { if (!vis[v]) { vis[v] = true; q.push(v); } } } } }; vector ans; for (const auto &q : queries) { g[q[0]].push_back(q[1]); ans.push_back(bfs(0)); } return ans; } }; ``` ### Python ```python class Solution: def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]: def bfs(i: int) -> int: q = deque([i]) vis = [False] * n vis[i] = True d = 0 while 1: for _ in range(len(q)): u = q . popleft() if u == n - 1: return d for v in g[u]: if not vis[v]: vis[v] = True q . append(v) d += 1 g = [[i + 1] for i in range(n - 1)] ans = [] for u, v in queries: g[u]. append(v) ans . append(bfs(0)) return ans ```