Skip to content

3244. Shortest Distance After Road Addition Queries II 👍

  • Time: $O(n + q)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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