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]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 between cities. After each addition, compute the shortest distance from city 0 to city n-1.
Approach 1: Breadth-First Search (BFS) Recompute per Query (Time: O(q*(n+e)), Space: O(n+e))
Maintain an adjacency list representing the current graph. Initially add edges i → i+1 for all cities. For every query (u, v), append the new edge to the adjacency list and run a Breadth-First Search starting from node 0. Since all roads have equal weight, BFS naturally finds the shortest number of edges to each city. The first time you reach n-1 gives the shortest path length. This approach is straightforward and works well because constraints keep the graph relatively small. Each query triggers a fresh traversal of the graph.
Approach 2: Dijkstra with Priority Queue (Time: O(q*(n+e) log n), Space: O(n+e))
Another option is running Dijkstra's Algorithm after each road insertion. Store the graph in an adjacency list and use a min-heap to always expand the node with the smallest current distance. Although all edges have weight 1 (making BFS slightly more efficient), Dijkstra provides a general solution for shortest paths and works even if weights change in future variations. After each query, push the start node 0 into the priority queue and relax edges until reaching n-1. The priority queue ensures nodes are processed in increasing distance order.
Recommended for interviews: BFS is typically expected because every road has equal weight. Running BFS after each query demonstrates understanding of shortest paths in unweighted graphs and keeps implementation simple. Mentioning the Dijkstra alternative shows awareness of weighted graph techniques and broader problem-solving skills.
This approach treats the problem as a graph traversal problem where each city is a node and roads are directed edges. Initially, the graph is linear, and each query introduces a single directed edge. We can use BFS to update and find the shortest path after each new road is added, recalculating the shortest path from node 0 to node n-1.
This Python function shortest_path accepts the number of cities, n, and the list of queries that represent new road additions. The function maintains a dynamic graph representation and repeatedly performs BFS to determine the new shortest path from city 0 to city n-1 after each query.
Python
JavaScript
Time Complexity: O(n * q), where n is the number of cities and q is the number of queries, due to the BFS traversal for each query.
Space Complexity: O(n + q), accounting for graph representation and BFS queue.
This approach models the problem as a weighted graph and uses Dijkstra's algorithm, which is suitable since the graph predominantly has unit weights. This algorithm efficiently finds the shortest path from the start city to the end city after each new road is introduced, leveraging a priority queue to always expand the shortest known total distance path.
This C++ implementation of Dijkstra's algorithm uses a priority queue to determine the shortest path efficiently. Initially, the graph is set up with each city i and i+1 connected. For each query, a new edge is added, and the Dijkstra's algorithm recalculates the shortest path.
Time Complexity: O((n + q) log n), due to the priority queue operations within Dijkstra’s algorithm for each query.
Space Complexity: O(n + q), needed for graph representation and distance calculations.
We first build a directed graph g, where g[i] represents the list of cities that can be reached from city i. Initially, each city i has a one-way road to city i + 1.
Then, for each query [u, v], we add v to the list of reachable cities from u, and then use BFS to find the shortest path length from city 0 to city n - 1, adding the result to the answer array.
Finally, we return the answer array.
The time complexity is O(q times (n + q)), and the space complexity is O(n + q). Here, n and q are the number of cities and the number of queries, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n * q), where n is the number of cities and q is the number of queries, due to the BFS traversal for each query. |
| Dijkstra's Algorithm with Priority Queue | Time Complexity: O((n + q) log n), due to the priority queue operations within Dijkstra’s algorithm for each query. |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search per Query | O(q*(n+e)) | O(n+e) | Best for unweighted graphs where each road has equal cost |
| Dijkstra with Priority Queue | O(q*(n+e) log n) | O(n+e) | General shortest-path solution or when edge weights vary |
Shortest Distance After Road Addition Queries I - Leetcode 3243 - Python • NeetCodeIO • 10,373 views views
Watch 9 more video solutions →Practice Shortest Distance After Road Addition Queries I with our built-in code editor and test cases.
Practice on FleetCode