# Shortest Distance After Road Addition Queries II
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-distance-after-road-addition-queries-ii)
Canonical: https://scaleengineer.com/dsa/problems/shortest-distance-after-road-addition-queries-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Graph, Ordered Set
---
## Problem
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:** 

![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-ii/image0.jpg)

After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.

![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-ii/image1.jpg)

After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.

![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-ii/image2.jpg)

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:**

![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-ii/image3.jpg)

After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.

![](https://assets.glich.co/dsa/shortest-distance-after-road-addition-queries-ii/image4.jpg)

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]`.

# Approaches
## Brute Force: Re-run BFS After Each Query
The most straightforward approach is to simulate the process directly. After each query adds a new road, the graph is modified. We can construct the graph with all roads up to the current query and then run a Breadth-First Search (BFS) starting from city `0` to find the shortest path to city `n-1`. Since all road lengths are 1, BFS is guaranteed to find the shortest path in terms of the number of roads.
**Time:** O(Q * (N + E)) where N is the number of cities and E is the number of edges. After `k` queries, `E = (N-1) + k`. So, the complexity is roughly O(Q * (N + Q)). Given N, Q <= 10^5, this is too slow. · **Space:** O(N + Q) to store the adjacency list and O(N) for the BFS queue and distance array.
**Pros:** Simple to understand and implement.; Correctly solves the problem by definition.
**Cons:** Highly inefficient due to redundant computations. The BFS is run from scratch for every query.
### Explanation
### Algorithm:
1.  Initialize an adjacency list to represent the graph. Add the initial roads `i -> i+1` for all `0 <= i < n-1`.
2.  Create an array `answer` to store the results.
3.  Iterate through each query `[u, v]`:
    a. Add the new directed edge `u -> v` to the adjacency list.
    b. Perform a BFS starting from the source city `0`:
        i.  Initialize a `distance` array of size `n` with a value indicating infinity (e.g., -1), and set `distance[0] = 0`.
        ii. Use a queue for BFS and add `0` to it.
        iii. While the queue is not empty, dequeue a city `curr`. If `curr` is `n-1`, we have found the shortest path length.
        iv. For each neighbor of `curr`, if it hasn't been visited (i.e., its distance is infinity), update its distance and enqueue it.
    c. After the BFS completes, `distance[n-1]` will hold the length of the shortest path from `0` to `n-1`. Store this value in the `answer` array.
4.  Return the `answer` array.

### Code Snippet:
```java
class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            adj.get(i).add(i + 1);
        }

        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            adj.get(queries[i][0]).add(queries[i][1]);

            int[] dist = new int[n];
            Arrays.fill(dist, -1);
            Queue<Integer> q = new LinkedList<>();

            dist[0] = 0;
            q.add(0);

            int pathLength = -1;
            while (!q.isEmpty()) {
                int u = q.poll();
                if (u == n - 1) {
                    pathLength = dist[u];
                    break;
                }
                for (int v : adj.get(u)) {
                    if (dist[v] == -1) {
                        dist[v] = dist[u] + 1;
                        q.add(v);
                    }
                }
            }
            result[i] = pathLength;
        }
        return result;
    }
}
```
### Algorithm
1.  Initialize an adjacency list to represent the graph. Add the initial roads `i -> i+1` for all `0 <= i < n-1`.
2.  Create an array `answer` to store the results.
3.  Iterate through each query `[u, v]`:
    a. Add the new directed edge `u -> v` to the adjacency list.
    b. Perform a BFS starting from the source city `0`:
        i.  Initialize a `distance` array of size `n` with a value indicating infinity (e.g., -1), and set `distance[0] = 0`.
        ii. Use a queue for BFS and add `0` to it.
        iii. While the queue is not empty, dequeue a city `curr`. If `curr` is `n-1`, we have found the shortest path length.
        iv. For each neighbor of `curr`, if it hasn't been visited (i.e., its distance is infinity), update its distance and enqueue it.
    c. After the BFS completes, `distance[n-1]` will hold the length of the shortest path from `0` to `n-1`. Store this value in the `answer` array.
4.  Return the `answer` array.

## Incremental DP on Nodes
Instead of rebuilding the graph and running a full BFS each time, we can maintain an array `dist` where `dist[i]` stores the shortest distance from city `0` to city `i`. Initially, `dist[i] = i`. After each query `[u, v]`, we only need to re-calculate the distances for cities from `v` onwards, as distances to cities before `v` cannot be improved by this new road. This can be framed as a dynamic programming problem.
**Time:** O(Q * (N + Q)). For each of the `Q` queries, we iterate from `i=1` to `N-1`. At each `i`, we might iterate through all `k` previous queries (where `k` is the current query index). This leads to a total complexity of roughly `sum_{k=1 to Q} O(N+k) = O(NQ + Q^2)`. · **Space:** O(Q) to store the queries and O(N) for the `dist` array.
**Pros:** Avoids the overhead of a full graph traversal data structure like a queue.; Conceptually builds upon the problem's path structure.
**Cons:** Still very inefficient and will time out for large inputs.; The inner loop checking all previous queries for each node is costly.
### Explanation
### Algorithm:
1.  Initialize an empty list of query edges seen so far.
2.  For each new query `[u, v]`:
    a. Add the query to the list of edges.
    b. Create a `dist` array of size `n` to compute the new shortest paths.
    c. Set `dist[0] = 0`.
    d. Iterate from `i = 1` to `n-1` to compute `dist[i]`:
        i. The default path is from `i-1`, so initialize `dist[i] = dist[i-1] + 1`.
        ii. Consider all query edges `(u_j, v_j)` added so far where `v_j == i`. For each such edge, there's a potential shorter path through `u_j`. Update `dist[i] = min(dist[i], dist[u_j] + 1)`.
    e. The shortest path to `n-1` is `dist[n-1]`. Add it to the results.

This approach re-calculates the entire `dist` array for each query, but it's slightly more optimized than a full BFS as it avoids explicit graph traversal overhead.

### Code Snippet:
```java
class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        int[] result = new int[queries.length];
        List<int[]> currentQueries = new ArrayList<>();

        for (int i = 0; i < queries.length; i++) {
            currentQueries.add(queries[i]);
            
            Map<Integer, List<Integer>> incomingEdges = new HashMap<>();
            for (int[] q : currentQueries) {
                incomingEdges.computeIfAbsent(q[1], k -> new ArrayList<>()).add(q[0]);
            }

            long[] dist = new long[n];
            dist[0] = 0;
            for (int j = 1; j < n; j++) {
                dist[j] = dist[j - 1] + 1;
                if (incomingEdges.containsKey(j)) {
                    for (int u : incomingEdges.get(j)) {
                        dist[j] = Math.min(dist[j], dist[u] + 1);
                    }
                }
            }
            result[i] = (int) dist[n - 1];
        }
        return result;
    }
}
```
### Algorithm
1.  Initialize an empty list of query edges seen so far.
2.  For each new query `[u, v]`:
    a. Add the query to the list of edges.
    b. Create a `dist` array of size `n` to compute the new shortest paths.
    c. Set `dist[0] = 0`.
    d. Iterate from `i = 1` to `n-1` to compute `dist[i]`:
        i. The default path is from `i-1`, so initialize `dist[i] = dist[i-1] + 1`.
        ii. Consider all query edges `(u_j, v_j)` added so far where `v_j == i`. For each such edge, there's a potential shorter path through `u_j`. Update `dist[i] = min(dist[i], dist[u_j] + 1)`.
    e. The shortest path to `n-1` is `dist[n-1]`. Add it to the results.

## Online Dynamic Programming on Queries with Segment Tree
The most efficient solution involves a different dynamic programming perspective. Instead of computing distances to each city, we define a DP state on the queries themselves. Let `dp[k]` be the length of the shortest path from city `0` to city `v_k`, with the constraint that the query `q_k = (u_k, v_k)` is the *last* shortcut taken. To calculate `dp[k]`, we need the shortest distance to `u_k`, which can be found by considering all prior shortcuts. This process can be optimized using a segment tree.
**Time:** O(Q * log N). For each of the `Q` queries, we perform one range query and one point update on the segment tree, both of which take O(log N) time. · **Space:** O(N + Q). O(N) for the segment tree and O(Q) for the result array.
**Pros:** Highly efficient and passes within the time limits.; Correctly solves the problem in an online fashion.; Demonstrates an advanced application of dynamic programming and data structures.
**Cons:** The DP formulation is non-trivial to derive.; Implementation of the segment tree adds complexity.
### Explanation
### DP Formulation:
The shortest path to any city `x` is `dist(0, x)`. A path can use the initial `i -> i+1` roads or any available query shortcuts. A path that uses shortcuts consists of segments of the initial path, connected by query edges.
Let `dp[k]` be the shortest path from `0` to `v_k` using query `k` as the last shortcut. This path looks like `0 -> ... -> u_k -> v_k`. The length is `dist(0, u_k) + 1`.
The shortest distance `dist(0, u_k)` is the minimum of taking the straight path (`u_k`) or using some previous query `j` (`j < k`) as a shortcut. If we use query `j=(u_j, v_j)`, the path is `0 -> ... -> v_j -> ... -> u_k`, with length `dp[j] + (u_k - v_j)`. We only consider queries where `v_j <= u_k`.
So, `dist(0, u_k) = min(u_k, min_{j<k, v_j <= u_k} (dp[j] + u_k - v_j))`. Rearranging, `dist(0, u_k) = u_k + min(0, min_{j<k, v_j <= u_k} (dp[j] - v_j))`. 
This gives the recurrence: `dp[k] = u_k + 1 + min(0, min_{j<k, v_j <= u_k} (dp[j] - v_j))`. 

### Algorithm with Segment Tree:
We can process queries online. For each query `k`, we need to find `min_{j<k, v_j <= u_k} (dp[j] - v_j)`. This is a range minimum query. We can use a segment tree for this. The segment tree will be built over city indices `0` to `n-1`.
1.  Initialize a segment tree of size `n` to handle range minimum queries and point updates. All values are initialized to infinity.
2.  Initialize `min_overall_cost = infinity` to track `min_{j=0..k} (dp[j] - v_j)`.
3.  For each query `k = (u_k, v_k)`:
    a. Query the segment tree for the minimum value in the range `[0, u_k]`. Let this be `m`.
    b. Calculate `dp[k] = u_k + 1 + min(0, m)`.
    c. Update the segment tree at index `v_k` with the value `dp[k] - v_k`. The update operation should be `min(current_value, new_value)`.
    d. Update the overall minimum: `min_overall_cost = min(min_overall_cost, dp[k] - v_k)`.
    e. The shortest path from `0` to `n-1` after query `k` is `(n-1) + min(0, min_overall_cost)`. Store this in the answer array.
4.  Return the answer array.

### Code Snippet:
```java
class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        SegmentTree st = new SegmentTree(n);
        int[] result = new int[queries.length];
        long minCostTerm = Long.MAX_VALUE / 2;

        for (int i = 0; i < queries.length; i++) {
            int u = queries[i][0];
            int v = queries[i][1];

            long m = st.query(0, u);
            long dp_i = (long)u + 1 + Math.min(0, m);

            st.update(v, dp_i - v);

            minCostTerm = Math.min(minCostTerm, dp_i - v);
            
            result[i] = (int)((long)n - 1 + Math.min(0, minCostTerm));
        }
        return result;
    }
}

class SegmentTree {
    long[] tree;
    int n;
    final long INF = Long.MAX_VALUE / 2;

    SegmentTree(int size) {
        n = size;
        tree = new long[4 * n];
        Arrays.fill(tree, INF);
    }

    void update(int idx, long val) {
        update(1, 0, n - 1, idx, val);
    }

    void update(int node, int start, int end, int idx, long val) {
        if (start == end) {
            tree[node] = Math.min(tree[node], val);
            return;
        }
        int mid = start + (end - start) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);
    }

    long query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    long query(int node, int start, int end, int l, int r) {
        if (r < start || end < l) {
            return INF;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        long p1 = query(2 * node, start, mid, l, r);
        long p2 = query(2 * node + 1, mid + 1, end, l, r);
        return Math.min(p1, p2);
    }
}
```
### Algorithm
We can process queries online. For each query `k`, we need to find `min_{j<k, v_j <= u_k} (dp[j] - v_j)`. This is a range minimum query. We can use a segment tree for this. The segment tree will be built over city indices `0` to `n-1`.
1.  Initialize a segment tree of size `n` to handle range minimum queries and point updates. All values are initialized to infinity.
2.  Initialize `min_overall_cost = infinity` to track `min_{j=0..k} (dp[j] - v_j)`.
3.  For each query `k = (u_k, v_k)`:
    a. Query the segment tree for the minimum value in the range `[0, u_k]`. Let this be `m`.
    b. Calculate `dp[k] = u_k + 1 + min(0, m)`.
    c. Update the segment tree at index `v_k` with the value `dp[k] - v_k`. The update operation should be `min(current_value, new_value)`.
    d. Update the overall minimum: `min_overall_cost = min(min_overall_cost, dp[k] - v_k)`.
    e. The shortest path from `0` to `n-1` after query `k` is `(n-1) + min(0, min_overall_cost)`. Store this in the answer array.
4.  Return the answer array.

# Solutions
### Java

```java
class Solution {
public
  int[] shortestDistanceAfterQueries(int n, int[][] queries) {
    int[] nxt = new int[n - 1];
    for (int i = 1; i < n; ++i) {
      nxt[i - 1] = i;
    }
    int m = queries.length;
    int cnt = n - 1;
    int[] ans = new int[m];
    for (int i = 0; i < m; ++i) {
      int u = queries[i][0], v = queries[i][1];
      if (nxt[u] > 0 && nxt[u] < v) {
        int j = nxt[u];
        while (j < v) {
          --cnt;
          int t = nxt[j];
          nxt[j] = 0;
          j = t;
        }
        nxt[u] = v;
      }
      ans[i] = cnt;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> shortestDistanceAfterQueries(int n,
                                           vector<vector<int>> &queries) {
    vector<int> nxt(n - 1);
    iota(nxt.begin(), nxt.end(), 1);
    int cnt = n - 1;
    vector<int> ans;
    for (const auto &q : queries) {
      int u = q[0], v = q[1];
      if (nxt[u] && nxt[u] < v) {
        int i = nxt[u];
        while (i < v) {
          --cnt;
          int t = nxt[i];
          nxt[i] = 0;
          i = t;
        }
        nxt[u] = v;
      }
      ans.push_back(cnt);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]: nxt = list(range(1, n)) ans = [] cnt = n - 1 for u, v in queries: if 0 < nxt[u] < v: i = nxt[u] while i < v: cnt -= 1 nxt[i], i = 0, nxt[i] nxt[u] = v ans . append(cnt) return ans

```