Problem Description

You have n cities numbered from 0 to n - 1. Initially, these cities are connected by one-way roads where each city i has a road going to city i + 1 (for all 0 <= i < n - 1). This forms a simple path from city 0 to city n - 1.

You're given a list of queries where each query queries[i] = [u_i, v_i] represents adding a new one-way road from city u_i to city v_i. These new roads act as shortcuts that can potentially reduce the travel distance between cities.

Your task is to process these queries one by one. After adding each new road, you need to find the shortest path from city 0 to city n - 1. The result should be an array where answer[i] represents the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

For example, if n = 5, initially you have roads: 0→1→2→3→4, giving a shortest path length of 4. If the first query adds a road from city 0 to city 3, then the new shortest path would be 0→3→4 with length 2.

The key points to understand:

• Roads are unidirectional (one-way only)
• Initially, there's a sequential path from city 0 to city n - 1
• Each query adds a new road that might create a shortcut
• You need to calculate the shortest path after each query is processed
• The path length is the number of roads traveled, not the number of cities visited

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves cities (nodes) connected by roads (edges). We have a directed graph where initially each city i connects to city i+1, and we're adding new edges with each query.

Is it a tree?

• No: The graph is not a tree because after adding new roads from queries, we can have multiple paths between cities and potentially create cycles.

Is the problem related to directed acyclic graphs?

• No: While the graph is directed, it's not specifically about DAG properties like topological ordering.

Is the problem related to shortest paths?

• Yes: We need to find the shortest path from city 0 to city n-1 after each query.

Is the graph weighted?

• No: All roads have the same weight (cost of 1). We're counting the number of roads traveled, not summing weights.

BFS

• Yes: Since we have an unweighted graph and need to find shortest paths, BFS is the appropriate algorithm.

Conclusion: The flowchart correctly leads us to use BFS (Breadth-First Search) for finding the shortest path in an unweighted directed graph. BFS guarantees finding the shortest path in terms of the number of edges when all edges have equal weight.

Intuition

When we think about this problem, we start with a simple chain of cities connected sequentially: 0→1→2→...→(n-1). Each query adds a new "shortcut" road that might help us reach the destination faster.

The key insight is that after adding each new road, we need to recalculate the shortest path because this new road might create a better route. Since all roads have the same "cost" (each road counts as 1 in the path length), this is an unweighted graph problem.

Why BFS? In an unweighted graph, BFS naturally finds the shortest path by exploring nodes level by level. When BFS first reaches a node, it's guaranteed to have found the shortest path to that node. This property makes BFS perfect for our problem.

Here's the thought process:

1. We maintain an adjacency list g where g[i] stores all cities directly reachable from city i
2. Initially, g[i] = [i+1] for all cities except the last one
3. For each query [u, v], we add v to g[u], creating a new road
4. After adding each road, we run BFS from city 0 to find the shortest distance to city n-1

The BFS works by:

• Starting from city 0 with distance 0
• Exploring all cities at distance 1, then distance 2, and so on
• When we first reach city n-1, we've found the shortest path

This approach is straightforward because we don't need to optimize for weighted edges or worry about negative cycles - we simply need to count the minimum number of "hops" from start to end after each road addition.

Learn more about Breadth-First Search and Graph patterns.

Solution Approach

The implementation follows a straightforward BFS approach with dynamic graph updates:

Graph Representation: We use an adjacency list g where g[i] is a list containing all cities directly reachable from city i. Initially, we build this graph with:

g = [[i + 1] for i in range(n - 1)]

This creates the initial roads where city i connects to city i + 1.

Processing Queries: For each query [u, v], we:

1. Add the new road by appending v to g[u]
2. Run BFS to find the new shortest distance from city 0 to city n-1
3. Store this distance in our answer array

BFS Implementation: The BFS function works as follows:

1. Initialization: Start with city 0 in the queue, mark it as visited, and set distance d = 0

2. Level-by-level exploration: Process all nodes at the current distance level before moving to the next level

   for _ in range(len(q)):
       u = q.popleft()

3. Target check: When we dequeue city n-1, we immediately return the current distance d as it's guaranteed to be the shortest

4. Neighbor exploration: For each unvisited neighbor v of the current city u:

   • Mark v as visited
   • Add v to the queue for the next level

5. Distance increment: After processing all nodes at the current level, increment d by 1

The use of a vis array prevents revisiting cities and ensures we find the shortest path. Since BFS explores nodes level by level, the first time we reach the destination is guaranteed to be via the shortest path.

Time Complexity: For each query, BFS takes O(n + edges) time. With q queries, the total time is O(q × (n + edges)).

Space Complexity: O(n) for the graph representation and BFS data structures.

Example Walkthrough

Let's walk through a small example with n = 5 cities and queries = [[0, 3], [2, 4]].

Initial Setup:

• Cities: 0, 1, 2, 3, 4
• Initial roads: 0→1, 1→2, 2→3, 3→4
• Graph representation: g = [[1], [2], [3], [4], []]
• Initial shortest path: 0→1→2→3→4 (length = 4)

Processing Query 1: [0, 3]

1. Add road from city 0 to city 3: g[0].append(3), so g = [[1, 3], [2], [3], [4], []]
2. Run BFS from city 0:
   • Start: queue = [0], visited = {0}, distance = 0
   • Level 0: Process city 0
     • Neighbors: 1 and 3 (both unvisited)
     • Add to queue: [1, 3], visited = {0, 1, 3}
   • Level 1: Process cities 1 and 3
     • From city 1: neighbor 2 (unvisited) → queue = [3, 2]
     • From city 3: neighbor 4 (unvisited) → queue = [2, 4]
     • Combined queue after level: [2, 4], visited = {0, 1, 2, 3, 4}
   • Level 2: Process cities 2 and 4
     • City 4 is our target (n-1)! Return distance = 2
3. New shortest path: 0→3→4 (length = 2)
4. Answer so far: [2]

Processing Query 2: [2, 4]

1. Add road from city 2 to city 4: g[2].append(4), so g = [[1, 3], [2], [3, 4], [4], []]
2. Run BFS from city 0:
   • Start: queue = [0], visited = {0}, distance = 0
   • Level 0: Process city 0
     • Neighbors: 1 and 3 → queue = [1, 3], visited = {0, 1, 3}
   • Level 1: Process cities 1 and 3
     • From city 1: neighbor 2 → queue = [3, 2]
     • From city 3: neighbor 4 → queue = [2, 4]
     • Combined queue after level: [2, 4], visited = {0, 1, 2, 3, 4}
   • Level 2: Process cities 2 and 4
     • City 4 is our target! Return distance = 2
3. Shortest path remains: 0→3→4 (length = 2)
   • Note: The new road 2→4 doesn't improve our shortest path
4. Final answer: [2, 2]

Key Observations:

• The first query created a significant shortcut, reducing the path from 4 to 2
• The second query didn't improve the shortest path since we already had a 2-hop route
• BFS efficiently finds the shortest path by exploring all cities at distance d before moving to distance d+1
• When BFS first encounters city n-1, we're guaranteed to have found the shortest path

Solution Implementation

Time and Space Complexity

Time Complexity: O(q × (n + q))

For each query, we perform a BFS traversal:

• BFS in the worst case visits all n nodes
• After processing q queries, each node can have at most q + 1 outgoing edges (1 original edge plus up to q added edges)
• Thus, the total number of edges after q queries is at most n - 1 + q
• Each BFS takes O(V + E) = O(n + (n - 1 + q)) = O(n + q) time
• Since we run BFS for each of the q queries, the total time complexity is O(q × (n + q))

Space Complexity: O(n + q)

The space usage consists of:

• Graph adjacency list g: Initially has n - 1 lists with 1 element each. After q queries, it can have up to n - 1 + q total edges stored, requiring O(n + q) space
• BFS queue q: Can contain at most n nodes at any time, requiring O(n) space
• Visited array vis: Always has exactly n boolean values, requiring O(n) space
• Result array ans: Stores q results, requiring O(q) space

The overall space complexity is O(n + q) as the graph storage dominates after multiple queries are added.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Graph Initialization

A frequent mistake is incorrectly initializing the adjacency list, especially forgetting that city n-1 has no outgoing edges initially.

Incorrect:

# This creates n lists instead of n-1
adjacency_list = [[i + 1] for i in range(n)]  # Wrong! Index n-1 would point to n

Correct:

# City n-1 has no outgoing edges initially
adjacency_list = [[i + 1] for i in range(n - 1)]

2. BFS Early Termination Logic

The current implementation checks if we've reached the destination after dequeuing, which is correct. A common mistake is checking before adding to the queue, which can lead to incorrect distance calculations.

Incorrect:

for neighbor in adjacency_list[current_node]:
    if neighbor == n - 1:
        return distance + 1  # Wrong! This might not be the shortest path
    if not visited[neighbor]:
        visited[neighbor] = True
        queue.append(neighbor)

Correct:

# Check after dequeuing to ensure we're processing at the correct distance level
if current_node == n - 1:
    return distance

3. Handling Edge Cases

The code assumes we'll always find a path (which is valid given the problem constraints). However, a more robust implementation should handle the case where no path exists or when n <= 1.

Enhanced Solution:

def bfs(start: int) -> int:
    if n <= 1:
        return 0
    if start == n - 1:
        return 0
      
    queue = deque([start])
    visited = [False] * n
    visited[start] = True
    distance = 0
  
    while queue:  # Changed from while True
        for _ in range(len(queue)):
            current_node = queue.popleft()
            if current_node == n - 1:
                return distance
          
            # Handle nodes that might not have outgoing edges
            if current_node < len(adjacency_list):
                for neighbor in adjacency_list[current_node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
        distance += 1
  
    return -1  # No path found (shouldn't happen in this problem)

4. Memory Optimization Consideration

While the current solution is correct, repeatedly creating a new visited array for each BFS call can be optimized by reusing a single array:

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        # Create reusable visited array
        self.visited = [False] * n
      
        def bfs(start: int) -> int:
            # Reset visited array instead of creating new one
            for i in range(n):
                self.visited[i] = False
            self.visited[start] = True
            # ... rest of BFS logic

This reduces memory allocation overhead when processing many queries.