We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Distance After Road Addition Queries I

Number: 3517

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

We are given n cities (numbered 0 to n-1) that are initially connected in a unidirectional chain (from city i to city i+1). Then, a sequence of queries is provided where each query adds a new unidirectional road from city u to city v (with u < v and v - u > 1). After each query the task is to calculate the length of the shortest path from city 0 to city n-1.

Key Insights

  • The initial configuration forms a simple chain ensuring a baseline path from 0 to n-1.
  • Each query introduces a shortcut that may reduce the distance dramatically.
  • Since the graph is directed and roads are only added (never removed), the graph grows monotonically.
  • Given the constraints (n and queries up to 500) it is feasible to run a Breadth-First Search (BFS) after processing each query.
  • BFS is ideal since all edges have equal weights and yields the shortest path in an unweighted graph.

Space and Time Complexity

Time Complexity: O(Q * (N + E)), where Q is the number of queries, N is the number of nodes, and E is the number of edges. In the worst-case, both N and E are around 500. Space Complexity: O(N + E) for storing the graph and auxiliary data structures used during BFS.

Solution

We build the graph initially with roads from city 0 to 1, 1 to 2, ..., up to n-2 to n-1. For each query, we add the new road to the graph, then run BFS starting at city 0 and stopping when we reach city n-1. The BFS guarantees that the first time we reach n-1, the path length is the minimum number of edges required. This process is repeated for every query and the result is stored in an answer array.

Key data structures:

  • An adjacency list (dictionary or vector) to represent the graph.
  • A queue for BFS.
  • A visited set (or array) to avoid reprocessing nodes.

Algorithm steps:

  1. Initialize the graph with the chain roads.
  2. For each query: a. Add the new road to the graph. b. Run a BFS from node 0 to search for node n-1. c. Record the shortest path distance.
  3. Return the list of shortest path lengths after each query.

Code Solutions

from collections import deque

def shortestPathAfterQueries(n, queries):
    # Build initial graph: road from i to i+1 for all 0 <= i < n-1
    graph = {i: [] for i in range(n)}
    for i in range(n - 1):
        graph[i].append(i + 1)
    
    def bfs():
        # Perform a BFS starting from node 0
        queue = deque([(0, 0)])  # (node, distance)
        visited = [False] * n
        visited[0] = True
        while queue:
            node, dist = queue.popleft()
            # If we reach the final node, return the distance
            if node == n - 1:
                return dist
            # Iterate over neighbors of the current node
            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append((neighbor, dist + 1))
        # With initial chain, this should not happen, but return -1 if unreachable
        return -1

    results = []
    # Process each query by adding the new road, then performing BFS.
    for u, v in queries:
        # Add the new road from u to v
        graph[u].append(v)
        # Compute the shortest path from node 0 to node n-1
        results.append(bfs())
    return results

# Example usage:
print(shortestPathAfterQueries(5, [[2,4],[0,2],[0,4]]))  # Output: [3,2,1]
← Back to All Questions