#3243

Medium

auto_awesomeGraph traversal with breadth-first search

LeetCode Problem Workspace

Shortest Distance After Road Addition Queries I

Solve shortest paths dynamically in a growing graph using BFS, updating distances efficiently after each road addition query.

array breadth first search graph

Problem Statement

You are given an integer n representing n cities labeled from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1. You are also given a list of queries where each query adds a new road between two cities.

Each query is represented as queries[i] = [ui, vi], which adds a road from city ui to city vi. After each road addition, you must return the length of the shortest path from city 0 to city n - 1 considering the current set of roads. If no path exists, return an appropriate indicator such as -1.

Examples

Example 1

Input: n = 5, queries = [[2,4],[0,2],[0,4]]

Output: [3,2,1]

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]

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 <= 500
1 <= queries.length <= 500
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
There are no repeated roads among the queries.

Solution Approach

Maintain an adjacency list for dynamic graph updates

Use an adjacency list to represent the graph, initially containing the linear roads. For each query, add the new road to this list to allow BFS to traverse the updated graph.

Perform BFS from city 0 after each query

After adding a road, run a BFS starting from city 0 to compute shortest distances to all reachable cities. Stop BFS early if city n - 1 is reached to save computation, tracking the minimum distance.

Record shortest paths incrementally

Store the shortest path length after each query in an array. This allows you to return results directly after processing all queries without recomputing or backtracking unnecessarily.

Complexity Analysis

Metric	Value
Time	O(q \times (n+q))
Space	O(n+q)

Time complexity is O(q * (n + q)) because each of the q queries may trigger a BFS exploring up to n nodes plus previously added q roads. Space complexity is O(n + q) to store the adjacency list for n nodes and all added roads.

What Interviewers Usually Probe

Check if the candidate efficiently updates the graph structure after each query.
Watch for early BFS termination when city n - 1 is found to optimize performance.
Listen for reasoning about incremental shortest path updates versus full recomputation.

Common Pitfalls or Variants

Common pitfalls

Recomputing the entire shortest path from scratch for every query without incremental tracking.
Ignoring early stopping in BFS and exploring unnecessary nodes.
Failing to handle cases where no path exists after a road addition.

Follow-up variants

Allow bidirectional road additions instead of unidirectional, requiring modified BFS.
Return the full shortest path sequence from 0 to n - 1 after each query instead of just the length.
Process a larger graph with sparse updates using a priority queue to improve BFS efficiency.

FAQ

What is the best approach to handle multiple road addition queries?

Maintain an adjacency list and perform BFS from city 0 after each addition to compute updated shortest paths efficiently.

Can this problem handle bidirectional roads?

Yes, but BFS logic must account for roads being traversable in both directions and update the adjacency list accordingly.

How do I optimize BFS for large n and multiple queries?

Use early stopping when city n - 1 is reached and avoid revisiting nodes already explored in the current BFS iteration.

What pattern does this problem primarily follow?

It follows the graph traversal with breadth-first search pattern, updating shortest paths dynamically after each road addition.

Why is incremental distance tracking important in this problem?

It avoids full recomputation of shortest paths for every query, saving time when multiple queries are applied sequentially.

terminal

Solution

Solution 1: BFS

We first build a directed graph $\textit{g}$, where $\textit{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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def shortestDistanceAfterQueries(
        self, n: int, queries: List[List[int]]
    ) -> List[int]:
        def bfs(i: int) -> int:
            q = deque([i])
            vis = [False] * n
            vis[i] = True
            d = 0
            while 1:
                for _ in range(len(q)):
                    u = q.popleft()
                    if u == n - 1:
                        return d
                    for v in g[u]:
                        if not vis[v]:
                            vis[v] = True
                            q.append(v)
                d += 1

        g = [[i + 1] for i in range(n - 1)]
        ans = []
        for u, v in queries:
            g[u].append(v)
            ans.append(bfs(0))
        return ans

Continue Practicing

#3286 find a safe walk through a grid #3387 maximize amount after two days of conversions #3493 properties graph