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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Distance After Road Addition Queries I

Difficulty: Medium

Problem Description

You are given an integer n and a 2D integer array queries. There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1. queries[i] = [u_i, v_i] represents the addition of a new unidirectional road from city u_i to city v_i. After each query, you need to find the length of the shortest path from city 0 to city n - 1. Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city n - 1 after processing the first i + 1 queries.

Key Insights

  • The initial graph is a linear path from city 0 to city n - 1.
  • Additional roads can create shortcuts, potentially reducing the shortest path length.
  • Each query modifies the graph, and we need to efficiently compute the shortest path after each modification.
  • The problem can be approached using a breadth-first search (BFS) or by maintaining an adjacency list that reflects the current state of the graph after each query.

Space and Time Complexity

Time Complexity: O(m * (n + q)), where m is the number of queries, n is the number of cities, and q is the average number of edges in the graph after processing queries. Space Complexity: O(n + m), where n is the number of cities and m is the number of edges in the graph.

Solution

To solve the problem, we can use an adjacency list to represent the graph of cities and roads. Initially, we create a list of roads based on the unidirectional roads from i to i + 1. For each query, we add a new road to the adjacency list. We then perform a BFS from city 0 to city n - 1 to find the shortest path length after each query. The BFS will explore the graph level by level, ensuring we find the shortest path efficiently.

Code Solutions

from collections import deque, defaultdict

def shortestDistance(n, queries):
    # Initialize the adjacency list
    graph = defaultdict(list)
    for i in range(n - 1):
        graph[i].append(i + 1)
    
    # Result list to store the shortest distances after each query
    result = []
    
    # Function to perform BFS to find shortest path from 0 to n-1
    def bfs():
        queue = deque([0])
        distances = {0: 0}
        
        while queue:
            current = queue.popleft()
            for neighbor in graph[current]:
                if neighbor not in distances:
                    distances[neighbor] = distances[current] + 1
                    queue.append(neighbor)

        return distances.get(n - 1, -1)  # Return -1 if unreachable
    
    # Process each query
    for u, v in queries:
        graph[u].append(v)  # Add the new road
        shortest_path_length = bfs()  # Get the shortest path length
        result.append(shortest_path_length)

    return result
← Back to All Questions