3243. Shortest Distance After Road Addition Queries I

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.

Approach 01:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

class Solution {
public:
    vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
        vector<int> result;
        vector<int> distances(n);
        vector<vector<int>> adjacencyList(n);

        // Initialize the distances and graph (adjacency list)
        for (int i = 0; i < n; ++i) {
            distances[i] = i;
        }

        for (int i = 0; i < n - 1; ++i) {
            adjacencyList[i].push_back(i + 1);
        }

        // Process each query
        for (const auto& query : queries) {
            int startNode = query[0];
            int endNode = query[1];
            adjacencyList[startNode].push_back(endNode);

            // Update distance and perform BFS if necessary
            if (distances[startNode] + 1 < distances[endNode]) {
                distances[endNode] = distances[startNode] + 1;
                bfs(adjacencyList, endNode, distances);
            }
            result.push_back(distances[n - 1]);
        }

        return result;
    }

private:
    void bfs(const vector<vector<int>>& adjacencyList, int startNode, vector<int>& distances) {
        queue<int> q;
        q.push(startNode);

        while (!q.empty()) {
            int currentNode = q.front();
            q.pop();

            for (int neighbor : adjacencyList[currentNode]) {
                if (distances[currentNode] + 1 < distances[neighbor]) {
                    distances[neighbor] = distances[currentNode] + 1;
                    q.push(neighbor);
                }
            }
        }
    }
};

import collections

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: list[list[int]]) -> list[int]:
        result = []
        distances = list(range(n))
        adjacencyList = [[] for _ in range(n)]

        # Initialize the graph (adjacency list)
        for i in range(n - 1):
            adjacencyList[i].append(i + 1)

        # Process each query
        for u, v in queries:
            adjacencyList[u].append(v)
            # Update distance and perform BFS if necessary
            if distances[u] + 1 < distances[v]:
                distances[v] = distances[u] + 1
                self._bfs(adjacencyList, v, distances)
            result.append(distances[n - 1])

        return result

    def _bfs(self, adjacencyList: list[list[int]], startNode: int, distances: list[int]) -> None:
        queue = collections.deque([startNode])
        while queue:
            currentNode = queue.popleft()
            for neighbor in adjacencyList[currentNode]:
                if distances[currentNode] + 1 < distances[neighbor]:
                    distances[neighbor] = distances[currentNode] + 1
                    queue.append(neighbor)

Time Complexity

• Initializing Distances:

  Initializing the distances vector and adjacency list takes \( O(N) \), where \( N \) is the number of nodes (vertices) in the graph.

• Processing Queries:

  For each query, we add a new edge to the adjacency list and potentially update the distances vector. The BFS is triggered only if a shorter path is found. The BFS itself processes all reachable nodes from the startNode, and in the worst case, it visits all \( N \) nodes.

• BFS Complexity:

  The BFS function has a worst-case time complexity of \( O(N + E) \), where \( E \) is the number of edges. Since in each query, the adjacency list is updated, the number of edges can grow, but in the worst case, the graph is fully connected, so \( E \approx N \).

• Overall Time Complexity:

  Since there are \( Q \) queries, and each query can trigger a BFS that visits all nodes and edges, the overall time complexity is \( O(Q \times (N + E)) \). In the worst case where the graph is fully connected, \( E \approx N \), so the time complexity becomes \( O(Q \times N) \).

Space Complexity

• Distances Vector:

  The distances vector takes \( O(N) \) space.

• Adjacency List:

  The adjacency list stores \( N \) nodes and at most \( E \) edges, requiring \( O(N + E) \) space.

• Queue for BFS:

  The queue used in the BFS function stores at most \( N \) nodes at any given time, requiring \( O(N) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(N + E) \), due to the adjacency list and the BFS queue. In the worst case, \( E \approx N \), so the space complexity becomes \( O(N) \).