Watch 8 video solutions for Shortest Distance After Road Addition Queries II, a hard level problem involving Array, Greedy, Graph. This walkthrough by Aryan Mittal has 2,071 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][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 <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]i != j and queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].Problem Overview: You start with n cities connected in a straight line where each city i has a road to i+1. Queries add new directed roads (u, v). After every addition, compute the shortest distance from city 0 to city n-1. The challenge is updating the shortest path efficiently as the graph changes repeatedly.
Approach 1: Dynamic Path Update with BFS (Time: O(q * (n + e)), Space: O(n + e))
Treat the cities and roads as a directed graph. Maintain an adjacency list that initially contains edges i → i+1. For each query, insert the new edge u → v and run a BFS from node 0 to recompute the shortest distance to n-1. BFS works because every edge has equal weight, so the first time you reach a node you have the optimal distance. This approach is simple and reliable but recomputes the path from scratch after every update, which becomes expensive when q grows.
Approach 2: Graph Updates with DJ-Set (Union-Find) (Time: ~O(n + q α(n)), Space: O(n))
The key observation: the original path is linear and queries only add forward edges u < v. When a shortcut u → v appears, the intermediate nodes between them may no longer contribute to the shortest path. Use a disjoint-set structure to "skip" nodes that become redundant. Maintain a next-pointer style structure (similar to an ordered set) where union operations compress consecutive nodes already bypassed by shortcuts. Each query effectively removes edges along the linear chain that are now unnecessary, decreasing the total path length. Path compression keeps operations nearly constant time, so across all queries the total work stays close to linear.
Recommended for interviews: Start with the BFS recomputation approach. It clearly models the dynamic graph and shows you understand shortest-path traversal. Then explain the observation that queries only add forward shortcuts and the base graph is linear. The Union-Find compression method leverages that structure to avoid recomputing BFS, reducing the complexity to near O(n + q). Interviewers usually expect recognition of this structural optimization rather than repeated graph traversal.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Graph BFS After Each Query | O(q * (n + e)) | O(n + e) | Good baseline approach when constraints are small or for explaining shortest-path logic in interviews |
| Union-Find Graph Compression | O(n + q α(n)) | O(n) | Optimal solution when many queries are present and the graph structure is mostly linear |