• Leetcode POTDs

Problem 3243 Shortest Distance After Road Addition Queries I

Problem Statement

Link - Problem 3243

Question

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] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. 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.

Example 1:

Example 2:

Constraints:

• 3 <= n <= 500
• 1 <= queries.length <= 500
• queries[i].length == 2
• 0 <= queries[i][0] < queries[i][1] < n
• 1 < queries[i][1] - queries[i][0]
• There are no repeated roads among the queries.

Solution

class Solution {
public:
    vector<vector<int>> graph;
    vector<int> distances;

    int computeShortestPath(int start_node, int total_nodes) {
        queue<int> bfs_queue;
        bfs_queue.push(start_node);

        while (!bfs_queue.empty()) {
            int curr_node = bfs_queue.front();
            bfs_queue.pop();

            for (const int& neighbor : graph[curr_node]) {
                if (distances[neighbor] > distances[curr_node] + 1) {
                    distances[neighbor] = distances[curr_node] + 1;
                    bfs_queue.push(neighbor);
                }
            }
        }

        return distances[total_nodes - 1];
    }

    vector<int> shortestDistanceAfterQueries(int total_nodes, vector<vector<int>>& queries) {
        graph.resize(total_nodes);
        for (int i = 0; i < total_nodes - 1; i++) {
            graph[i].push_back(i + 1);
        }

        distances.resize(total_nodes);
        iota(distances.begin(), distances.end(), 0);
        // iota is used to prevent loops like this
        // for (int i = 0; i < n; ++i) {
                //distances[i] = i;
            //}
        vector<int> result;
        result.reserve(queries.size());
        for (const auto& query : queries) {
            graph[query[0]].push_back(query[1]);
            result.push_back(computeShortestPath(query[0], total_nodes));
        }

        return result;
    }
};

Complexity Analysis

| Algorithm                      | Time Complexity | Space Complexity |
| ------------------------------ | --------------- | ---------------- |
| Unweighted Shortest Path (BFS) | O(nq)           | O(n)             |

Explanation

1. Intuition

• The problem can be solved using a graph and a breadth-first search (BFS) algorithm.
• We can represent the cities as nodes in the graph and the roads as directed edges.
• The shortest path from city 0 to city n-1 can be found by performing a BFS from city 0.
• We can use a queue to keep track of the nodes to visit next.
• We can use a distances array to keep track of the shortest distance from city 0 to each city.
• We can update the distances array as we visit each node.
• We can return the shortest distance from city 0 to city n-1 after each query.

2. Implementation

• We initialize the graph with n nodes and add a directed edge from each node to the next node.
• We initialize the distances array with the initial distances from city 0 to each city.
• We use the iota function to initialize the distances array with the initial distances.
• We iterate over the queries and add a directed edge from the start node to the end node.
• We call the computeShortestPath function to update the distances array and return the shortest distance.
• We use a queue to perform the BFS and update the distances array.
• We use the push_back function to add nodes to the queue and the pop function to remove nodes from the queue.
• We use the resize function to resize the graph and distances array.

Complexity Analysis

Time Complexity:

• The time complexity is O(n*q) due to the nested loops in the shortestDistanceAfterQueries function. The outer loop iterates over queries, which is of size q, and the inner loop contains the computeShortestPath function that performs BFS over the graph. The BFS traversal has a time complexity of O(n) because it visits each node at most once.
• The computeShortestPath function has a time complexity of O(n) since it visits each node at most once. This is because the bfs_queue only adds nodes that haven’t been visited yet, ensuring a linear traversal of the graph.
• The shortestDistanceAfterQueries function also reserves memory for the result vector and initialises the graph, but these operations have a constant time complexity. Therefore, the overall time complexity is dominated by the nested loops.

Space Complexity:

• The space complexity is O(n) due to the storage required by the graph and distances vectors. The graph is of size n, where each element is another vector that has an average size of n/total_nodes, but in the worst case, it can be as big as n.
• The distances vector also requires O(n) space as it stores the shortest distance from each node to the destination. The result vector in shortestDistanceAfterQueries requires O(q) space but it’s not considered as part of the overall space complexity because it’s the output of the function.
• The bfs_queue used in the computeShortestPath function has a maximum size of n in the worst case when the graph is fully connected. This contributes to the overall space complexity of O(n).

Footnote

This question is rated as Medium difficulty.

Hints

Maintain the graph and use an efficient shortest path algorithm after each update.

We use BFS/Dijkstra for each query.