Problem of The Day: Shortest Distance After Road Addition Queries I
Problem Statement
Intuition
To solve this problem, the goal is to find the shortest path between two nodes in a graph after each query. Initially, the graph is a directed chain where each node is connected to its next one. After each query, a new directed edge is added between two nodes. The task is to calculate the shortest distance from the source node (0) to the destination node (n-1) after each query.
The problem can be approached using a breadth-first search (BFS) because BFS guarantees that we find the shortest path in an unweighted graph. However, as the graph is updated after each query, we must recompute the shortest distance after each addition of a new edge.
Approach
-
Initial Setup: We start by initializing a graph where each node points to the next node in the sequence. The graph is represented as an adjacency list. For example, for
n = 5, the initial graph would be{0: [1], 1: [2], 2: [3], 3: [4], 4: []}. -
Breadth-First Search (BFS): For each query, which specifies a new edge from
srctodest, we perform BFS to find the shortest path from node0to noden-1. BFS works by exploring the graph level by level, ensuring that once we reach the destination noden-1, the path we took is the shortest. -
Handling Queries: After each query, we add the edge from
srctodestto the graph and perform BFS again to compute the new shortest path. -
Recomputing After Each Query: After processing each query, we store the result (the shortest path distance) and proceed to the next query. This is done for every query in the list of queries.
-
Edge Cases:
- If the graph is disconnected or if no path exists from node 0 to node
n-1, BFS will return the maximum possible steps (though this situation should ideally be handled in the code).
- If the graph is disconnected or if no path exists from node 0 to node
Complexity
-
Time complexity:
Each query requires performing BFS, which has a time complexity of \(O(n + m)\), wherenis the number of nodes andmis the number of edges in the graph. Since we perform BFS for each query, the total time complexity is \(O(q \cdot (n + m))\), whereqis the number of queries. -
Space complexity:
The space complexity is dominated by the storage required for the graph and the BFS queue. The graph uses \(O(n + m)\) space, and the queue and visited set used in BFS also require \(O(n)\) space. Therefore, the total space complexity is \(O(n + m)\).
Code
from collections import deque
from typing import List
class Solution:
def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
# Initial graph setup: each node points to the next node in sequence.
graph = {i: [i + 1] for i in range(n)}
# BFS to find the shortest path from node 0 to node n-1
def bfs():
q = deque([[0, 0]]) # Start from node 0 with 0 steps
visited = set() # Set to track visited nodes
while q:
node, step = q.popleft()
if node == n - 1: # If we reach the last node, return the steps
return step
for nei in graph[node]:
if nei not in visited:
visited.add(nei)
q.append([nei, step + 1])
return step # If no path exists, return the last known step
# List to store results for each query
res = []
# Process each query, add the new edge and compute shortest distance
for src, dest in queries:
graph[src].append(dest) # Add the edge as per the query
res.append(bfs()) # Perform BFS and append the result
return res
Editorial
Approach 1: Breadth First Search (BFS)
class Solution:
# Helper function to perform BFS and find the number of edges in the shortest path from node 0 to node n-1
def bfs(self, n: int, adj_list: List[List[int]]) -> int:
visited = [False] * n
node_queue = deque()
# Start BFS from node 0
node_queue.append(0)
visited[0] = True
# Track the number of nodes in the current layer and the next layer
current_layer_node_count = 1
next_layer_node_count = 0
# Initialize layers explored count
layers_explored = 0
# Perform BFS until the queue is empty
while node_queue:
# Process nodes in the current layer
for _ in range(current_layer_node_count):
current_node = node_queue.popleft()
# Check if we reached the destination node
if current_node == n - 1:
return layers_explored # Return the number of edges in the shortest path
# Explore all adjacent nodes
for neighbor in adj_list[current_node]:
if visited[neighbor]:
continue
node_queue.append(
neighbor
) # Add neighbor to the queue for exploration
next_layer_node_count += (
1 # Increment the count of nodes in the next layer
)
visited[neighbor] = True
# Move to the next layer
current_layer_node_count = next_layer_node_count
next_layer_node_count = 0 # Reset next layer count
layers_explored += 1 # Increment the layer count after processing the current layer
return -1 # Algorithm will never reach this point
def shortestDistanceAfterQueries(
self, n: int, queries: List[List[int]]
) -> List[int]:
answer = []
adj_list = [[] for _ in range(n)]
# Initialize the graph with edges between consecutive nodes
for i in range(n - 1):
adj_list[i].append(i + 1)
# Process each query to add new roads
for road in queries:
u, v = road
adj_list[u].append(v) # Add road from u to v
# Perform BFS to find the shortest path after adding the new road
answer.append(self.bfs(n, adj_list))
return answer
Approach 2: Recursive Dynamic Programming (Top-Down)
class Solution:
# Recursive function to find the minimum distance from the current node to
# the destination node (n-1)
def find_min_distance(self, adj_list, n, current_node, dp):
# We've reached the destination node
if current_node == n - 1:
return 0
# If this node has already been computed, return the stored value
if dp[current_node] != -1:
return dp[current_node]
min_distance = n
for neighbor in adj_list[current_node]:
# Recursively find the minimum distance from the neighbor to the destination
min_distance = min(
min_distance,
self.find_min_distance(adj_list, n, neighbor, dp) + 1,
)
# Store the computed minimum distance in the dp array and return it
dp[current_node] = min_distance
return min_distance
def shortestDistanceAfterQueries(self, n, queries):
dp = [-1] * n # DP array to store minimum distances from each node
adj_list = [[] for _ in range(n)]
# Initialize the graph with edges between consecutive nodes
for i in range(n - 1):
adj_list[i].append(i + 1)
answer = []
# Process each query to add new edges
for road in queries:
u = road[0]
v = road[1]
# Add the directed edge from u to v
adj_list[u].append(v)
# Find the minimum distance from the starting node (0) to the destination (n-1)
answer.append(self.find_min_distance(adj_list, n, 0, dp))
# Clear and reset the dp array
dp = [-1] * n
return answer # Return the results for each query
Approach 3: Iterative Dynamic Programming (Bottom-Up)
class Solution:
# Function to find the minimum distance from node 0 to node n-1
def find_min_distance(self, adj_list, n):
dp = [0] * n
dp[n - 1] = 0 # Base case: distance to destination (n-1) is 0
# Iterate from the second last node down to the first node
for current_node in range(n - 2, -1, -1):
min_distance = n
# Explore neighbors to find the minimum distance
for neighbor in adj_list[current_node]:
min_distance = min(min_distance, dp[neighbor] + 1)
# Store the calculated distance for the current node
dp[current_node] = min_distance
return dp[0]
def shortestDistanceAfterQueries(self, n, queries):
answer = []
adj_list = [[] for _ in range(n)]
# Initialize edges between consecutive nodes
for i in range(n - 1):
adj_list[i].append(i + 1)
# Process each query to add new edges
for road in queries:
u, v = road[0], road[1]
adj_list[u].append(v) # Add the directed edge from u to v
# Calculate the minimum distance after adding the new edge
answer.append(self.find_min_distance(adj_list, n))
return answer
