Facebook Pixel

3243. Shortest Distance After Road Addition Queries I

MediumBreadth-First SearchGraphArray
Leetcode Link

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.

Each element 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.

Intuition

To tackle this problem, consider the initial setup of cities and roads as a directed path from city 0 to n - 1. Each city i is directly connected to city i + 1. In this structure, the shortest path from 0 to n - 1 is the straightforward traversal of these roads, which amounts to a path length of n - 1.

With each query [u_i, v_i], we effectively introduce a new road, potentially altering the shortest path between the cities. The task is to dynamically update the shortest path length as each query modifies the graph.

Using a Breadth-First Search (BFS) approach is intuitive here. BFS is optimal for finding the shortest path in an unweighted graph, which fits our scenario. After each query, we:

  1. Update the graph to include the new road from u_i to v_i.
  2. Use BFS starting from city 0 to determine the shortest path length to city n - 1.
  3. Record the result after each query in our answer list.

This approach ensures that we incorporate changes to the graph in real time and efficiently compute the shortest path after each modification. The BFS explores the graph layer by layer, guaranteeing the shortest path discovery without necessitating more complex traversal methods.

Learn more about Breadth-First Search and Graph patterns.

Solution Approach

The solution employs a Breadth-First Search (BFS) strategy to determine the shortest path from city 0 to city n - 1 in a dynamic graph setting where new roads are added incrementally.

  1. Graph Initialization:

    • Begin by constructing a directed graph g, represented as an adjacency list. Initially, each city i is connected by a road to city i + 1 (i.e., g[i] = [i + 1] for 0 <= i < n - 1).

  2. Processing Queries:

    • For each query [u_i, v_i], append v_i to the list of destinations from city u_i. This effectively adds a new road from u_i to v_i in the graph g.

  3. Breadth-First Search (BFS):

    • Define a helper function bfs(i) to perform the BFS from a given starting city i:
      • Utilize a queue to facilitate the level-order traversal. Initialize it with the starting city 0 and mark it as visited.
      • Maintain a distance counter d to keep track of the current path length.
      • While the queue is not empty:
        • Process all nodes at the current depth by iterating over the queue.
        • For each city u dequeued, check if it is city n - 1. If so, return the current distance d as the shortest path.
        • Otherwise, explore its neighbors from the adjacency list g[u]. For each unvisited city v, mark it as visited and enqueue it.
      • Increment the distance counter d after exploring all nodes at the current level, effectively moving to the next level.

  4. Result Compilation:

    • For each query, invoke the bfs(0) function to compute the shortest path to city n - 1 given the latest graph modifications.
    • Collect the resulting path length into the answer list.

The BFS ensures that we always compute the shortest path accurately due to its level-wise expansion, which naturally prioritizes shorter paths. This systematic approach efficiently updates the solution with each query processed.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple example to illustrate the solution approach.

Initial Setup:

  • Number of cities, n = 4.
  • Queries: [[2, 3], [1, 3]].

Initially, the cities and roads form a straight path:

  • Roads: 0 -> 1 -> 2 -> 3
  • The shortest path from city 0 to city 3 is simply the direct traversal: 0 -> 1 -> 2 -> 3, resulting in a length of 3.

Processing Queries:

  1. First Query [2, 3]:

    • Add a new road from city 2 to city 3.
    • Updated roads:
      • 0 -> 1 -> 2 -> 3
      • 2 -> 3
    • The shortest path is still 0 -> 1 -> 2 -> 3 with a length of 3.
    • Append 3 to the answer list: answer = [3].

  2. Second Query [1, 3]:

    • Add a new road from city 1 to city 3.
    • Updated roads:
      • 0 -> 1 -> 2 -> 3
      • 2 -> 3
      • 1 -> 3
    • The path 0 -> 1 -> 3 is now the shortest path, with a length of 2.
    • Append 2 to the answer list: answer = [3, 2].

Final Answer:

  • After processing all queries, the results recorded are [3, 2], representing the shortest path lengths after each query update.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def shortestDistanceAfterQueries(
6        self, n: int, queries: List[List[int]]
7    ) -> List[int]:
8        # This function performs a Breadth-First Search (BFS) to find the shortest
9        # distance from node 'i' to the last node in the graph, which is node 'n-1'.
10        def bfs(start_node: int) -> int:
11            queue = deque([start_node])  # Initialize a queue with the start node.
12            visited = [False] * n  # This list keeps track of visited nodes.
13            visited[start_node] = True  # Mark the start node as visited.
14            distance = 0  # Initialize distance from start node.
15
16            while True:
17                # Process all nodes at the current level.
18                for _ in range(len(queue)):
19                    current_node = queue.popleft()
20
21                    # If the last node is reached, return the distance.
22                    if current_node == n - 1:
23                        return distance
24
25                    # Explore all adjacent nodes (neighbors) of the current node.
26                    for neighbor in graph[current_node]:
27                        # If the neighbor hasn't been visited yet, mark it and add it to the queue.
28                        if not visited[neighbor]:
29                            visited[neighbor] = True
30                            queue.append(neighbor)
31
32                # Increment the distance after exploring all nodes at the current level.
33                distance += 1
34
35        # Initialize the adjacency list representation for a linear graph.
36        graph = [[i + 1] for i in range(n - 1)]
37
38        results = []
39        for u, v in queries:
40            # Add the new directed edge to the graph from node u to node v.
41            graph[u].append(v)
42
43            # Compute and store the shortest distance from node 0 to node n-1 after the current query.
44            results.append(bfs(0))
45
46        return results
47
1import java.util.*;
2
3class Solution {
4    private List<Integer>[] graph; // Adjacency list to represent the graph
5    private int nodeCount; // Number of nodes in the graph
6
7    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
8        this.nodeCount = n; 
9        graph = new List[n];
10
11        // Initialize each node's adjacency list
12        Arrays.setAll(graph, i -> new ArrayList<>());
13
14        // Connect each node i to node i+1 (forming an initial path)
15        for (int i = 0; i < n - 1; ++i) {
16            graph[i].add(i + 1);
17        }
18
19        int numQueries = queries.length;
20        int[] result = new int[numQueries];
21
22        // Process each query to add an edge and compute shortest path
23        for (int i = 0; i < numQueries; ++i) {
24            int u = queries[i][0], v = queries[i][1];
25            graph[u].add(v); // Add the edge from u to v
26            result[i] = bfs(0); // Perform BFS to find shortest path from node 0 to node n-1
27        }
28
29        return result;
30    }
31
32    private int bfs(int startNode) {
33        Deque<Integer> queue = new ArrayDeque<>();
34        queue.offer(startNode); // Start BFS from the root node
35        boolean[] visited = new boolean[nodeCount]; 
36        visited[startNode] = true; 
37
38        for (int distance = 0;; ++distance) {
39            for (int k = queue.size(); k > 0; --k) {
40                int currentNode = queue.poll();
41                if (currentNode == nodeCount - 1) { // Check if we've reached the last node
42                    return distance; // Return the distance once the destination is reached
43                }
44                // Explore all neighbors of the current node
45                for (int neighbor : graph[currentNode]) {
46                    if (!visited[neighbor]) { // If the neighbor hasn't been visited
47                        visited[neighbor] = true; // Mark as visited
48                        queue.offer(neighbor); // Add to queue for further exploration
49                    }
50                }
51            }
52        }
53    }
54}
55
1#include <vector>
2#include <queue>
3
4using namespace std;
5
6class Solution {
7public:
8    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
9        // Initialize a graph with n nodes
10        vector<int> graph[n];
11      
12        // Create a path from each node to the next in a straight-line manner
13        for (int i = 0; i < n - 1; ++i) {
14            graph[i].push_back(i + 1);
15        }
16      
17        // Lambda function to perform Breadth-First Search (BFS) from node i
18        auto bfs = [&](int startNode) -> int {
19            queue<int> q;
20            q.push(startNode);
21            vector<bool> visited(n, false);
22            visited[startNode] = true;
23          
24            // Initialize distance as 0
25            for (int distance = 0;; ++distance) {
26                // Process all nodes at the current distance level
27                for (int nodesAtCurrentLevel = q.size(); nodesAtCurrentLevel > 0; --nodesAtCurrentLevel) {
28                    int currentNode = q.front();
29                    q.pop();
30                  
31                    // If the last node is reached, return the distance
32                    if (currentNode == n - 1) {
33                        return distance;
34                    }
35                  
36                    // Enqueue all unvisited adjacent nodes
37                    for (int adjacentNode : graph[currentNode]) {
38                        if (!visited[adjacentNode]) {
39                            visited[adjacentNode] = true;
40                            q.push(adjacentNode);
41                        }
42                    }
43                }
44            }
45        };
46      
47        // Initialize a result vector to store shortest distances for each query
48        vector<int> result;
49      
50        // Process each query and update the graph
51        for (const auto& query : queries) {
52            int fromNode = query[0], toNode = query[1];
53            graph[fromNode].push_back(toNode);
54          
55            // Calculate shortest path from node 0 to node n-1 after each query
56            result.push_back(bfs(0));
57        }
58      
59        // Return the resulting distances
60        return result;
61    }
62};
63
1function shortestDistanceAfterQueries(n: number, queries: number[][]): number[] {
2    // Create an adjacency list to represent the graph.
3    const graph: number[][] = Array.from({ length: n }, () => []);
4
5    // Initially connect each node i to i+1 to form a path from 0 to n-1.
6    for (let i = 0; i < n - 1; ++i) {
7        graph[i].push(i + 1);
8    }
9
10    // Perform a Breadth-First Search (BFS) starting from node 0.
11    const bfs = (start: number): number => {
12        const queue: number[] = [start];
13        const visited: boolean[] = Array(n).fill(false);
14        visited[start] = true;
15
16        for (let distance = 0; ; ++distance) {
17            const nextQueue: number[] = [];
18
19            for (const currentNode of queue) {
20                // If we reach node n-1, return the distance.
21                if (currentNode === n - 1) {
22                    return distance;
23                }
24
25                // Explore neighboring nodes.
26                for (const neighbor of graph[currentNode]) {
27                    if (!visited[neighbor]) {
28                        visited[neighbor] = true;
29                        nextQueue.push(neighbor);
30                    }
31                }
32            }
33
34            queue.splice(0, queue.length, ...nextQueue);
35        }
36    };
37
38    const result: number[] = [];
39
40    // Process each query by adding the edge, then compute shortest path.
41    for (const [start, end] of queries) {
42        graph[start].push(end);
43        result.push(bfs(0));
44    }
45
46    return result;
47}
48

Time and Space Complexity

The time complexity of the provided code can be understood through its operations for each query. For each query, the code performs a Breadth-First Search (BFS) starting from city 0:

  • Constructing the graph g in the beginning takes O(n) time as it initializes the list of lists.
  • For each query, appending the new edge to the graph takes O(1) time.
  • The BFS operation from the start node until the last node is reached involves visiting all nodes and edges. In the worst case, this takes O(n + \text{edges in } g), which effectively becomes O(n + q) due to the accumulation of edges from multiple queries.

Thus, handling all queries results in a time complexity of (O(q \times (n + q))).

The space complexity involves:

  • The graph g, which can hold up to O(n + q) edges after all queries.
  • The BFS needs additional space for the queue and the visited array, both of size O(n).

Consequently, the overall space complexity is (O(n + q)).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

In a binary min heap, the minimum element can be found in:

Recommended Readings

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More