LeetCode 3243 - Shortest Distance After Road Addition Queries I

LeetCode Problem 3243

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Graph Theory

Solution

Problem Understanding

We are given n cities labeled from 0 to n - 1. Initially, the graph forms a simple directed chain:

• 0 -> 1
• 1 -> 2
• 2 -> 3
• ...
• n - 2 -> n - 1

This means that before processing any queries, the shortest path from city 0 to city n - 1 is always n - 1, because we must move one step at a time along the chain.

Each query adds one extra directed road u -> v, where u < v. After adding each road, we must compute the shortest distance from city 0 to city n - 1.

The important detail is that roads are added permanently. Every query modifies the graph for all future queries.

The output should contain one integer per query. The i-th result represents the shortest path length after processing queries 0 through i.

The constraints are relatively small:

• n <= 500
• queries.length <= 500

This tells us that an O(n^2) or even O(q * n^2) solution is completely acceptable.

The graph is always directed and acyclic because every edge satisfies u < v. This means all roads move forward only, never backward. That property simplifies shortest path computation significantly.

Several edge cases are important:

• A query may directly connect 0 to n - 1, immediately making the answer 1.
• A newly added edge may not improve the shortest path at all.
• Multiple shortcut edges may combine together to create a much shorter route.
• Since roads are directed, u -> v does not imply v -> u.
• The graph is guaranteed to have no duplicate added roads.

Approaches

Brute Force Approach

The most straightforward solution is to rebuild the graph after every query and run Breadth First Search from node 0 to node n - 1.

Because every edge has equal weight 1, BFS correctly computes the shortest path length in an unweighted graph.

The process would be:

1. Start with the original chain graph.
2. After each query, add the new edge.
3. Run BFS from node 0.
4. Record the shortest distance to node n - 1.

This works because BFS explores nodes level by level, guaranteeing the first time we reach a node is through the shortest path.

However, this repeatedly recomputes distances from scratch after every query.

If there are q queries, and each BFS takes O(n + e), the total complexity becomes approximately O(q * (n + e)).

Given the small constraints, this is actually fast enough.

Better Observation

Since the graph is always directed forward and relatively small, we can maintain an adjacency list and simply rerun BFS after each query.

This is already efficient enough for the constraints.

There is no need for complicated dynamic shortest path algorithms because:

• n is only 500
• queries.length is only 500
• BFS on such a graph is extremely cheap

The key insight is that the graph is unweighted, so BFS gives shortest paths optimally.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(q × (n + e))	O(n + e)	Rebuilds shortest path using BFS after every query
Optimal	O(q × (n + e))	O(n + e)	Incrementally maintains graph and runs BFS efficiently

Since e is at most about n + q, the practical upper bound is very small.

Algorithm Walkthrough

1. Create an adjacency list representing the graph.

Initially, for every city i from 0 to n - 2, add a directed edge from i to i + 1. 2. Prepare an answer array.

This array will store the shortest path length after each query. 3. Process queries one by one.

For each query [u, v], append v to the adjacency list of u. 4. Run BFS starting from node 0.

Use a queue to process nodes in increasing distance order. 5. Maintain a distance array.

Initialize all distances to -1 to indicate unvisited nodes.

Set distance[0] = 0. 6. While the queue is not empty:

• Remove the front node.

• Explore all outgoing neighbors.

• If a neighbor has not been visited:

• Set its distance.

• Push it into the queue.

7. Once BFS finishes, record distance[n - 1].

This is the shortest path length from city 0 to city n - 1. 8. Repeat for every query.

Why it works

BFS always explores nodes in order of shortest distance from the source in an unweighted graph.

Because every road has equal cost 1, the first time BFS reaches a node, it has found the shortest possible path to that node.

Since we rerun BFS after every graph update, the computed distance to n - 1 is always correct for the current graph configuration.

Python Solution

from collections import deque
from typing import List

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]

        # Initial chain edges
        for i in range(n - 1):
            graph[i].append(i + 1)

        def bfs() -> int:
            distance = [-1] * n
            distance[0] = 0

            queue = deque([0])

            while queue:
                current = queue.popleft()

                for neighbor in graph[current]:
                    if distance[neighbor] == -1:
                        distance[neighbor] = distance[current] + 1
                        queue.append(neighbor)

            return distance[n - 1]

        answer = []

        for u, v in queries:
            graph[u].append(v)
            answer.append(bfs())

        return answer

The solution begins by constructing the initial directed chain graph. Each node i has an edge to i + 1.

The bfs() helper function computes the shortest path from 0 to n - 1.

A distance array tracks the shortest known distance to each node. Unvisited nodes remain -1.

The queue drives the BFS traversal. Every time we visit a neighbor for the first time, we assign its shortest distance and push it into the queue.

After processing a query, we immediately run BFS again and append the resulting shortest distance to the answer list.

Because the graph size is small, repeatedly running BFS is efficient and easy to implement correctly.

Go Solution

package main

import "container/list"

func shortestDistanceAfterQueries(n int, queries [][]int) []int {
	graph := make([][]int, n)

	// Initial chain edges
	for i := 0; i < n-1; i++ {
		graph[i] = append(graph[i], i+1)
	}

	bfs := func() int {
		dist := make([]int, n)

		for i := 0; i < n; i++ {
			dist[i] = -1
		}

		dist[0] = 0

		queue := list.New()
		queue.PushBack(0)

		for queue.Len() > 0 {
			front := queue.Front()
			queue.Remove(front)

			current := front.Value.(int)

			for _, neighbor := range graph[current] {
				if dist[neighbor] == -1 {
					dist[neighbor] = dist[current] + 1
					queue.PushBack(neighbor)
				}
			}
		}

		return dist[n-1]
	}

	answer := make([]int, 0, len(queries))

	for _, query := range queries {
		u, v := query[0], query[1]

		graph[u] = append(graph[u], v)

		answer = append(answer, bfs())
	}

	return answer
}

The Go implementation follows the same structure as the Python version.

The BFS queue uses container/list, since Go does not provide a built in queue structure.

The distance array is initialized with -1 values to indicate unvisited nodes.

Slices are used for adjacency lists, which naturally support appending newly added edges.

There are no integer overflow concerns because the maximum distance is at most n - 1, which is only 499.

Worked Examples

Example 1

Input:

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

Initial graph:

0 -> 1 -> 2 -> 3 -> 4

Initial shortest distance:

0 -> 1 -> 2 -> 3 -> 4 = 4

Query 1: Add edge 2 -> 4

Graph:

0 -> 1 -> 2 -> 3 -> 4
           \
            -> 4

BFS traversal:

Node Visited	Distance
0	0
1	1
2	2
3	3
4	3

Shortest path:

0 -> 1 -> 2 -> 4

Answer becomes:

3

Query 2: Add edge 0 -> 2

Graph:

0 -> 1 -> 2 -> 3 -> 4
 \         \
  -> 2      -> 4

BFS traversal:

Node Visited	Distance
0	0
1	1
2	1
3	2
4	2

Shortest path:

0 -> 2 -> 4

Answer becomes:

2

Query 3: Add edge 0 -> 4

Graph:

0 -> 1 -> 2 -> 3 -> 4
|         \
|          -> 4
|
-> 2
|
-> 4

BFS traversal:

Node Visited	Distance
0	0
1	1
2	1
4	1

Shortest path:

0 -> 4

Answer becomes:

1

Final output:

[3,2,1]

Example 2

Input:

n = 4
queries = [[0,3],[0,2]]

Initial graph:

0 -> 1 -> 2 -> 3

Query 1: Add edge 0 -> 3

Shortest path:

0 -> 3

Distance:

1

Query 2: Add edge 0 -> 2

Possible paths:

0 -> 3 = 1
0 -> 2 -> 3 = 2

Shortest path remains:

1

Final output:

[1,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(q × (n + e))	BFS runs after every query
Space	O(n + e)	Adjacency list, queue, and distance array

Here:

• q is the number of queries
• e is the number of edges

Initially, there are n - 1 edges, and each query adds one more edge.

Since both n and q are at most 500, the maximum graph size is tiny, making repeated BFS completely acceptable.

Test Cases

from typing import List

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        from collections import deque

        graph = [[] for _ in range(n)]

        for i in range(n - 1):
            graph[i].append(i + 1)

        def bfs():
            dist = [-1] * n
            dist[0] = 0

            queue = deque([0])

            while queue:
                node = queue.popleft()

                for nei in graph[node]:
                    if dist[nei] == -1:
                        dist[nei] = dist[node] + 1
                        queue.append(nei)

            return dist[n - 1]

        answer = []

        for u, v in queries:
            graph[u].append(v)
            answer.append(bfs())

        return answer

sol = Solution()

assert sol.shortestDistanceAfterQueries(
    5,
    [[2, 4], [0, 2], [0, 4]]
) == [3, 2, 1]  # Provided example 1

assert sol.shortestDistanceAfterQueries(
    4,
    [[0, 3], [0, 2]]
) == [1, 1]  # Provided example 2

assert sol.shortestDistanceAfterQueries(
    3,
    [[0, 2]]
) == [1]  # Direct shortcut from start to end

assert sol.shortestDistanceAfterQueries(
    6,
    [[1, 3], [2, 5]]
) == [4, 3]  # Multiple improving shortcuts

assert sol.shortestDistanceAfterQueries(
    6,
    [[1, 4], [2, 4], [3, 5]]
) == [3, 3, 3]  # Later edges do not improve answer

assert sol.shortestDistanceAfterQueries(
    7,
    [[0, 3], [3, 6]]
) == [4, 2]  # Chained shortcuts combine

assert sol.shortestDistanceAfterQueries(
    5,
    [[1, 3]]
) == [3]  # Shortcut in middle only

assert sol.shortestDistanceAfterQueries(
    8,
    [[0, 4], [4, 7], [2, 6]]
) == [4, 2, 2]  # Existing shortest path remains optimal

Test	Why
[[2,4],[0,2],[0,4]]	Validates progressive shortening
[[0,3],[0,2]]	Ensures shortest path can remain unchanged
[[0,2]]	Tests direct start to end shortcut
[[1,3],[2,5]]	Verifies multiple improvements
[[1,4],[2,4],[3,5]]	Tests non improving additions
[[0,3],[3,6]]	Confirms shortcuts can combine
[[1,3]]	Tests middle graph optimization
[[0,4],[4,7],[2,6]]	Ensures old shortest path is preserved

Edge Cases

One important edge case occurs when a query directly connects city 0 to city n - 1. In this scenario, the shortest possible answer becomes 1, and no future query can improve it further. A buggy implementation might continue searching unnecessarily or incorrectly overwrite the optimal result. BFS handles this naturally because the direct edge is explored immediately.

Another important case is when a newly added edge does not improve the shortest path at all. For example, if the graph already contains a shorter route, adding another longer shortcut should not change the answer. Since BFS always computes the globally shortest path from scratch, it correctly ignores non beneficial edges.

A third important edge case involves combining shortcuts across multiple queries. A single shortcut might not help much initially, but after another edge is added later, together they may create a dramatically shorter path. Incremental greedy approaches can fail here if they only consider local improvements. Running BFS after every query guarantees that all available paths are considered globally.

A final subtle case is the directional nature of edges. Since every road is one way, accidentally treating the graph as undirected would produce incorrect distances. The implementation only appends edges in the forward direction, ensuring correctness.