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.
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); } } } } }}Video 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.