Skip to main content
Back to problems
#3244
Hard Algorithms

Shortest distance after road addition queries ii

Array Greedy Graph Theory Ordered Set
26.5% acceptance
Feb 25, 2026
208
6
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.

Solution

Rust
Time O(n²)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn shortest_distance_after_queries(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    // Track "active" nodes on the shortest path. Initially all n nodes are relevant.
    // Current shortest distance = (number of active nodes - 1).
    // Adding edge (u, v): all strictly interior nodes u+1 .. v-1 become irrelevant (bypassed).
    // Use a BTreeSet to efficiently find and remove those nodes.
    let mut active: std::collections::BTreeSet<i32> = (0..n as i32).collect();
    let mut dist = (n - 1) as i32;
    let mut result = Vec::with_capacity(queries.len());

    for q in &queries {
      let u = q[0];
      let v = q[1];
      // Remove all nodes strictly between u and v
      let to_remove: Vec<i32> = active.range((u + 1)..v).copied().collect();
      dist -= to_remove.len() as i32;
      for node in to_remove {
        active.remove(&node);
      }
      result.push(dist);
    }
    result
  }
}