Shortest Distance After Road Addition Queries I — Solution
Shortest Distance After Road Addition Queries I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Shortest Distance After Road Addition Queries I is a medium coding problem on arrays, breadth-first search and graph, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Breadth-First Search, Graph
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n cities numbered 0 to n - 1. At the start, the only roads are one-way roads from city i to city i + 1 for every 0 <= i < n - 1.
Each query queries[i] = [ui, vi] adds a new one-way road from ui to vi. Roads are never removed.
Return an array answer where answer[i] is the length (number of roads) of the shortest path from city 0 to city n - 1 after the first i + 1 queries have been applied.
Example 1
Input: n = 5, queries = [[2,4],[0,2],[0,4]]
Output: [3,2,1]
Explanation: After [2,4] the route 0→1→2→4 uses 3 roads; after [0,2] the route 0→2→4 uses 2; after [0,4] one road is enough.
Example 2
Input: n = 4, queries = [[0,3],[0,2]]
Output: [1,1]
Explanation: The road 0→3 already gives length 1, and the second road cannot improve on it.
Example 3
Input: n = 3, queries = [[0,2]]
Output: [1]
Constraints
3 <= n <= 5001 <= queries.length <= 500queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]no road is added twice
Hints for Shortest Distance After Road Addition Queries I
Hint 1
With at most 500 cities and 500 queries you can afford to recompute the shortest path from scratch after every query.
Hint 2
Every road goes from a smaller city to a larger one, so the cities in increasing order are already a topological order of the graph.
Hint 3
Keep each city's outgoing roads in a list. After adding a road, set
dist[0] = 0, walk the cities in order and relaxdist[y] = min(dist[y], dist[x] + 1)along every roadx → y(a BFS works just as well).
How to solve Shortest Distance After Road Addition Queries I
The limits are small enough to rebuild the answer after each query. Because every road points forward, one pass over the cities in increasing order computes all shortest distances from city 0.
Approach
- Start with
out[i] = [i + 1]for every city except the last. - For each query
[u, v], appendvtoout[u]. - Set
dist[0] = 0and every other entry to infinity; forxfrom 0 ton - 1, relaxdist[y]through each roadx → y. - Record
dist[n - 1].
Why it works
A road only leads to a larger city, so by the time city x is processed every road into it has already been relaxed and dist[x] is final — the usual DAG shortest-path argument. Since the original chain is always there, city n - 1 is always reachable.
Complexity
- Time —
O(q · (n + q)) - Space —
O(n + q)
Pitfalls
- Roads are one-way: a query
[u, v]never helps you travel fromvback tou. - Adding a road can leave the answer unchanged, as in the second example — record the distance after every query anyway.
Reference solution
Python
from typing import List
def shortestDistanceAfterQueries(n: int, queries: List[List[int]]) -> List[int]:
out = [[i + 1] for i in range(n - 1)] + [[]]
ans = []
for u, v in queries:
out[u].append(v)
dist = [n] * n
dist[0] = 0
for x in range(n):
d = dist[x] + 1
for y in out[x]:
if d < dist[y]:
dist[y] = d
ans.append(dist[n - 1])
return ansJava
public static int[] shortestDistanceAfterQueries(int n, int[][] queries) {
List<List<Integer>> out = new ArrayList<>();
for (int i = 0; i < n; i++) {
out.add(new ArrayList<>());
if (i + 1 < n) out.get(i).add(i + 1);
}
int[] ans = new int[queries.length];
int[] dist = new int[n];
for (int k = 0; k < queries.length; k++) {
out.get(queries[k][0]).add(queries[k][1]);
Arrays.fill(dist, n);
dist[0] = 0;
for (int x = 0; x < n; x++) {
int d = dist[x] + 1;
for (int y : out.get(x)) if (d < dist[y]) dist[y] = d;
}
ans[k] = dist[n - 1];
}
return ans;
}C++
vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
vector<vector<int>> out(n);
for (int i = 0; i + 1 < n; i++) out[i].push_back(i + 1);
vector<int> ans, dist(n);
for (auto& q : queries) {
out[q[0]].push_back(q[1]);
fill(dist.begin(), dist.end(), n);
dist[0] = 0;
for (int x = 0; x < n; x++) {
int d = dist[x] + 1;
for (int y : out[x]) if (d < dist[y]) dist[y] = d;
}
ans.push_back(dist[n - 1]);
}
return ans;
}JavaScript
var shortestDistanceAfterQueries = function(n, queries) {
var out = [];
for (var i = 0; i < n; i++) out.push(i + 1 < n ? [i + 1] : []);
var ans = [];
for (var k = 0; k < queries.length; k++) {
out[queries[k][0]].push(queries[k][1]);
var dist = [];
for (var j = 0; j < n; j++) dist.push(n);
dist[0] = 0;
for (var x = 0; x < n; x++) {
var d = dist[x] + 1;
for (var t = 0; t < out[x].length; t++) if (d < dist[out[x][t]]) dist[out[x][t]] = d;
}
ans.push(dist[n - 1]);
}
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Breadth-First Search (BFS)