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.
This approach utilizes BFS to update and compute the shortest path length from city 0 to city n-1 after each road addition. The BFS ensures that we efficiently manage path updates by traversing the shortest possible paths and updating distances as we encounter new shortcuts.
The Python solution employs a Breadth-First Search (BFS) to determine the shortest path length from city 0 to city n-1 after each new road is added. We maintain an adjacency list to represent the directed graph. For each query, we add the new road to the adjacency list and then use BFS to find the shortest path distance. This distance is collected and returned as the result.
Time Complexity: O(q * (n + E)), where q is the number of queries and E is the number of edges. Space Complexity: O(n + E) due to the adjacency list and distance tracking.
This approach uses a Disjoint Set Union (DSU), also known as Union-Find, to manage the connectivity between nodes (cities). We explore each query and attempt to track connected components to adjust and check path lengths from city 0 to city n-1.
The C++ solution uses a disjoint set data structure to manage the connected components of the graph. With each query, it attempts to unite the specified cities and checks if city 0 and city n-1 belong to the same connected component. If they are connected, it adds '1' to the result, otherwise, it calculates the additional path cost.
C++
JavaScript
Time Complexity: O(q * α(n)), where q is the number of queries and α is the Inverse Ackermann function. Space Complexity: O(n) for the DSU structure.
We define an array nxt of length n - 1, where nxt[i] represents the next city that can be reached from city i. Initially, nxt[i] = i + 1.
For each query [u, v], if u' and v' have already been connected before, and u' leq u < v leq v', then we can skip this query. Otherwise, we need to set the next city number for cities from nxt[u] to nxt[v - 1] to 0, and set nxt[u] to v.
During this process, we maintain a variable cnt, which represents the length of the shortest path from city 0 to city n - 1. Initially, cnt = n - 1. Each time we set the next city number for cities in [nxt[u], v) to 0, cnt decreases by 1.
Time complexity is O(n + q), and space complexity is O(n). Here, n and q are the number of cities and the number of queries, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Path Update with BFS | Time Complexity: O(q * (n + E)), where q is the number of queries and E is the number of edges. Space Complexity: O(n + E) due to the adjacency list and distance tracking. |
| Graph Updates with DJ-Set (Union-Find) | Time Complexity: O(q * α(n)), where q is the number of queries and α is the Inverse Ackermann function. Space Complexity: O(n) for the DSU structure. |
| Greedy + Recording Jump Positions | — |
| 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 |
3243 & 3244. Shortest Distance After Road Addition Queries I & II | Graph | BFS | Ordered Set • Aryan Mittal • 2,071 views views
Watch 7 more video solutions →Practice Shortest Distance After Road Addition Queries II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor