3243. Shortest Distance After Road Addition Queries I LeetCode Solution
In this guide, you will get 3243. Shortest Distance After Road Addition Queries I LeetCode Solution with the best time and space complexity. The solution to Shortest Distance After Road Addition Queries I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Shortest Distance After Road Addition Queries I solution in C++
- Shortest Distance After Road Addition Queries I solution in Java
- Shortest Distance After Road Addition Queries I solution in Python
- Additional Resources
Problem Statement of 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:
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.
Complexity Analysis
- Time Complexity: O(q(n + q))
- Space Complexity: O(n + q)
3243. Shortest Distance After Road Addition Queries I LeetCode Solution in C++
class Solution {
public:
vector<int> shortestDistanceAfterQueries(int n,
vector<vector<int>>& queries) {
vector<int> ans;
vector<int> dist(n);
vector<vector<int>> graph(n);
iota(dist.begin(), dist.end(), 0);
for (int i = 0; i < n - 1; ++i)
graph[i].push_back(i + 1);
for (const vector<int>& query : queries) {
const int u = query[0];
const int v = query[1];
graph[u].push_back(v);
if (dist[u] + 1 < dist[v]) {
dist[v] = dist[u] + 1;
bfs(graph, v, dist);
}
ans.push_back(dist[n - 1]);
}
return ans;
}
private:
// Performs a BFS to update the shortest distances from the given `start` node
// to all other reachable nodes in the graph. It updates the `dist` vector
// with the new shortest distances.
void bfs(const vector<vector<int>>& graph, int start, vector<int>& dist) {
queue<int> q{{start}};
while (!q.empty()) {
const int u = q.front();
q.pop();
for (const int v : graph[u]) {
if (dist[u] + 1 < dist[v]) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
};
/* code provided by PROGIEZ */3243. Shortest Distance After Road Addition Queries I LeetCode Solution in Java
class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
int[] ans = new int[queries.length];
int[] dist = new int[n];
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; ++i) {
dist[i] = i;
graph[i] = new ArrayList<>();
}
for (int i = 0; i < n - 1; ++i)
graph[i].add(i + 1);
for (int i = 0; i < queries.length; ++i) {
final int u = queries[i][0];
final int v = queries[i][1];
graph[u].add(v);
if (dist[u] + 1 < dist[v]) {
dist[v] = dist[u] + 1;
bfs(graph, v, dist);
}
ans[i] = dist[n - 1];
}
return ans;
}
// Performs a BFS to update the shortest distances from the given `start` node
// to all other reachable nodes in the graph. It updates the `dist` vector
// with the new shortest distances.
private void bfs(List<Integer>[] graph, int start, int[] dist) {
Queue<Integer> q = new LinkedList<>(Arrays.asList(start));
while (!q.isEmpty()) {
final int u = q.poll();
for (final int v : graph[u]) {
if (dist[u] + 1 < dist[v]) {
dist[v] = dist[u] + 1;
q.offer(v);
}
}
}
}
}
// code provided by PROGIEZ3243. Shortest Distance After Road Addition Queries I LeetCode Solution in Python
class Solution:
def shortestDistanceAfterQueries(
self,
n: int,
queries: list[list[int]],
) -> list[int]:
ans = []
dist = list(range(n))
graph = [[] for _ in range(n)]
for i in range(n - 1):
graph[i].append(i + 1)
for u, v in queries:
graph[u].append(v)
if dist[u] + 1 < dist[v]:
dist[v] = dist[u] + 1
self._bfs(graph, v, dist)
ans.append(dist[n - 1])
return ans
def _bfs(self, graph: list[list[int]], start: int, dist: list[int]) -> None:
"""
Performs a BFS to update the shortest distances from the given `start` node
to all other reachable nodes in the graph. It updates the `dist` vector
with the new shortest distances.
"""
q = collections.deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if dist[u] + 1 < dist[v]:
dist[v] = dist[u] + 1
q.append(v)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.