3244. Shortest Distance After Road Addition Queries II LeetCode Solution
In this guide, you will get 3244. Shortest Distance After Road Addition Queries II LeetCode Solution with the best time and space complexity. The solution to Shortest Distance After Road Addition Queries II 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.
Problem Statement of Shortest Distance After Road Addition Queries II
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.
There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][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 <= 105
1 <= queries.length <= 105
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.
There are no two queries such that i != j and queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].
Complexity Analysis
Time Complexity: O(n + q)
Space Complexity: O(n)
3244. Shortest Distance After Road Addition Queries II LeetCode Solution in C++
class Solution {
public:
vector<int> shortestDistanceAfterQueries(int n,
vector<vector<int>>& queries) {
vector<int> ans;
unordered_map<int, int> nodeToFarthestNode;
for (int i = 0; i < n - 1; ++i)
nodeToFarthestNode[i] = i + 1;
for (const vector<int>& query : queries) {
const int u = query[0];
const int v = query[1];
// If `u` exists in the map and `v` is farther than the current farthest
// node for `u`, we need to update the map and remove intermediate nodes.
if (nodeToFarthestNode.contains(u) && nodeToFarthestNode[u] < v) {
int node = nodeToFarthestNode[u];
while (node < v) {
const int cache = node;
node = nodeToFarthestNode[node];
nodeToFarthestNode.erase(cache);
}
nodeToFarthestNode[u] = v;
}
ans.push_back(nodeToFarthestNode.size());
}
return ans;
}
}; /* code provided by PROGIEZ */
3244. Shortest Distance After Road Addition Queries II LeetCode Solution in Java
class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
int[] ans = new int[queries.length];
Map<Integer, Integer> nodeToFarthestNode = new HashMap<>();
for (int i = 0; i < n - 1; ++i)
nodeToFarthestNode.put(i, i + 1);
for (int i = 0; i < queries.length; ++i) {
final int u = queries[i][0];
final int v = queries[i][1];
// If `u` exists in the map and `v` is farther than the current farthest
// node for `u`, we need to update the map and remove intermediate nodes.
if (nodeToFarthestNode.containsKey(u) && nodeToFarthestNode.get(u) < v) {
int node = nodeToFarthestNode.get(u);
while (node < v)
node = nodeToFarthestNode.remove(node);
nodeToFarthestNode.put(u, v);
}
ans[i] = nodeToFarthestNode.size();
}
return ans;
}
} // code provided by PROGIEZ
3244. Shortest Distance After Road Addition Queries II LeetCode Solution in Python
class Solution:
def shortestDistanceAfterQueries(
self,
n: int,
queries: list[list[int]],
) -> list[int]:
ans = []
nodeToFarthestNode = {i: i + 1 for i in range(n - 1)}
for u, v in queries:
# If `u` exists in the map and `v` is farther than the current farthest
# node for `u`, we need to update the map and remove intermediate nodes.
if u in nodeToFarthestNode and nodeToFarthestNode[u] < v:
node = nodeToFarthestNode[u]
while node < v:
node = nodeToFarthestNode.pop(node)
nodeToFarthestNode[u] = v
ans.append(len(nodeToFarthestNode))
return ans # code by PROGIEZ
