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:
Input: n = 5, queries = [[2,4],[0,2],[0,4]]
Output: [3,2,1]
Explanation:
After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.
Example 2:
Input: n = 4, queries = [[0,3],[0,2]]
Output: [1,1]
Explanation:
After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
After the addition of the road from 0 to 2, the length of the shortest path remains 1.
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:
-
C++
-
Python
#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) \).