Shortest Distance After Road Addition Queries I

Medium
1720.

Shortest Distance After Road Addition Queries I

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.

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 <= 500
  • 1 <= queries.length <= 500
  • queries[i].length == 2
  • 0 <= queries[i][0] < queries[i][1] < n
  • 1 < queries[i][1] - queries[i][0]
  • no road is added twice
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} queries
 * @return {number[]}
 */
var shortestDistanceAfterQueries = function(n, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 500
  • 1 <= queries.length <= 500
  • queries[i].length == 2
  • 0 <= queries[i][0] < queries[i][1] < n
  • 1 < queries[i][1] - queries[i][0]
  • no road is added twice

Hints for Shortest Distance After Road Addition Queries I

  1. Hint 1

    With at most 500 cities and 500 queries you can afford to recompute the shortest path from scratch after every query.

  2. 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.

  3. 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 relax dist[y] = min(dist[y], dist[x] + 1) along every road x → 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

  1. Start with out[i] = [i + 1] for every city except the last.
  2. For each query [u, v], append v to out[u].
  3. Set dist[0] = 0 and every other entry to infinity; for x from 0 to n - 1, relax dist[y] through each road x → y.
  4. 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 from v back to u.
  • 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 ans

Java

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)