Shortest Distance After Road Addition Queries I
MedPrompt
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:
After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
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:
After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
After the addition of the road from 0 to 2, the length of the shortest path remains 1.
Constraints:
3 <= n <= 5001 <= queries.length <= 500queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]- There are no repeated roads among the queries.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- For each query
ifrom0toqueries.length - 1:- Create an
n x ndistance matrixdist, initialized with infinity, except fordist[j][j] = 0. - Populate
distwith initial edges:dist[j][j+1] = 1for0 <= j < n-1. - Populate
distwith query edges from0toi:dist[u][v] = 1for each query[u, v]. - Apply the Floyd-Warshall algorithm to compute all-pairs shortest paths.
- Store
dist[0][n-1]as the answer for queryi.
- Create an
Walkthrough
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:
- Initialize an
n x ndistance matrixdist.dist[i][j]is 1 if there's a direct road fromitoj,0ifi == j, and infinity otherwise. - The initial roads
i -> i+1are added to the matrix. - For the
k-th query, all roads fromqueries[0]toqueries[k]are added. - The Floyd-Warshall algorithm is then run on this matrix. It iterates through all possible intermediate vertices
kfor each pair of sourceiand destinationj, and updates the shortest pathdist[i][j]if the path throughkis shorter. - 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.
class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { int[] answer = new int[queries.length]; java.util.List<int[]> 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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize an adjacency list
adjforncities. - Add the initial roads
i -> i+1toadj. - For each query
ifrom0toqueries.length - 1: a. Add the new roadqueries[i][0] -> queries[i][1]toadj. b. Perform a BFS starting from city 0. i. Use a queue and adistancearray, initialized to -1 (or infinity). ii.distance[0] = 0, push 0 to the queue. iii. While the queue is not empty, dequeue a cityu, and for each neighborv, ifvis unvisited, update its distance and enqueue it. c. The shortest path length isdistance[n-1]. Store it in the answer array.
Walkthrough
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:
- Start with a graph containing the initial roads
i -> i+1. - For each query
[u, v], add the new directed edgeu -> vto the adjacency list. - After adding the edge, perform a BFS starting from the source city, 0.
- BFS explores the graph layer by layer, guaranteeing that we find the shortest path to all reachable cities.
- During the BFS, we keep track of distances in a
distarray.dist[j]stores the shortest distance from city 0 to cityj. - 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 thanO(V^3). We avoid re-building the graph from scratch by incrementally adding edges.
class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { int[] answer = new int[queries.length]; java.util.List<java.util.List<Integer>> 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<java.util.List<Integer>> adj) { int[] dist = new int[n]; java.util.Arrays.fill(dist, -1); java.util.Queue<Integer> 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 }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
d0[i] = ianddn[i] = n-1-i. - Initialize
adjandrevAdjlists with the initiali -> i+1roads. - For each query
(u, v): a. Add edgeu -> vtoadjandv -> utorevAdj. b. Check ifd0[u] + 1 < d0[v]. If so, updated0[v]and start a BFS-like propagation fromvusingadjto updated0for successors. c. Check ifdn[v] + 1 < dn[u]. If so, updatedn[u]and start a BFS-like propagation fromuusingrevAdjto updatednfor predecessors. d. The answer for the current query is the updatedd0[n-1].
Walkthrough
We maintain two distance arrays:
d0[i]: shortest distance from city 0 to cityi.dn[i]: shortest distance from cityito cityn-1. Initially, with only roadsi -> i+1,d0[i] = ianddn[i] = (n-1) - i. For each query(u, v):
- The new road
u -> vmight create shorter paths. We must update ourd0anddnarrays to reflect this for future queries. - Updating
d0: The new road provides a new path tovof lengthd0[u] + 1. If this is shorter than the currentd0[v], we updated0[v]and propagate this change to all cities reachable fromv. This propagation can be done with a BFS-like procedure starting fromv. - Updating
dn: Similarly, the new road provides a new path fromuton-1(viav) of length1 + dn[v]. If this is shorter thandn[u], we updatedn[u]and propagate this change backward to all cities that can reachu. This is done with a BFS-like procedure on the graph with reversed edges, starting fromu. - After the updates,
d0[n-1]will hold the true shortest path length from 0 ton-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.
class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { int[] answer = new int[queries.length]; java.util.List<java.util.List<Integer>> adj = new java.util.ArrayList<>(); java.util.List<java.util.List<Integer>> 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<Integer> 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<Integer> 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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
class Solution {private List<Integer>[] 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<Integer> 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); } } } } }}class Solution {public: vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>> &queries) { vector<int> g[n]; for (int i = 0; i < n - 1; ++i) { g[i].push_back(i + 1); } auto bfs = [&](int i) -> int { queue<int> q{{i}}; vector<bool> 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<int> ans; for (const auto &q : queries) { g[q[0]].push_back(q[1]); ans.push_back(bfs(0)); } return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.