Problem statement

There are n cities numbered 0 to n - 1. At the start, the only roads are one-way roads from city i to city i + 1 for every 0 <= i < n - 1.

Each query queries[i] = [ui, vi] adds a new one-way road from ui to vi. The queries never cross each other: there are no two queries i and j with queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].

Return an array answer where answer[i] is the length (number of roads) of the shortest path from city 0 to city n - 1 after the first i + 1 queries have been applied.

Example 1

Input: n = 5, queries = [[2,4],[0,2],[0,4]]
Output: [3,2,1]
Explanation: The shortest route becomes 0→1→2→4, then 0→2→4, then 0→4.

Example 2

Input: n = 4, queries = [[0,3],[0,2]]
Output: [1,1]
Explanation: The road 0→2 lies inside the stretch 0→3 already skips, so it changes nothing.

Example 3

Input: n = 6, queries = [[1,3],[3,5],[0,5]]
Output: [4,3,1]

Constraints

• 3 <= n <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] < queries[i][1] < n
• 1 < queries[i][1] - queries[i][0]
• no road is added twice
• no two queries cross as described above

Hints for Shortest Distance After Road Addition Queries II

1. Hint 1

   Because the new roads never cross, two roads are either disjoint or one lies entirely inside the other. A road nested inside a stretch that is already skipped can never help.

2. Hint 2

   So the shortest path is always the chain of cities that have not been jumped over yet. Keep, for every city on that chain, the next city on it.

3. Hint 3

   For a query [u, v]: if u is still on the chain and its next city is before v, remove every city strictly between u and v (each city is removed at most once) and point u at v. The answer is the number of roads left on the chain.

How to solve Shortest Distance After Road Addition Queries II

Non-crossing roads make the best route a single forward chain: once a stretch is skipped, everything nested inside it is irrelevant. Maintain that chain as a linked list of next pointers and count its roads; each city leaves the chain at most once, so all queries together cost linear time.

Approach

1. Set next[i] = i + 1 for every city and roads = n - 1.
2. For a query [u, v]: if u has been removed (next[u] = -1) or next[u] >= v, the road changes nothing.
3. Otherwise walk i = next[u] while i < v: remember next[i], mark next[i] = -1, decrement roads, move on. Then set next[u] = v.
4. Append roads to the answer.

Why it works

Induction on the queries: the chain always holds the shortest route, and every skipped city lies strictly inside some road on the chain. A new road whose start was skipped lies inside that skipping road (crossing is forbidden), so it cannot shorten anything. A road from a chain city u lands on a chain city v for the same reason, so replacing the cities between them with one road is exactly the improvement it brings.

Complexity

• Time — O(n + q)
• Space — O(n)

Pitfalls

• A road starting at a removed city must be ignored — following its stale next pointer would corrupt the chain.
• If next[u] is already at or beyond v, the new road is shorter than one already used; do nothing.
• Recomputing a BFS per query, as in part I, is O(q · n) and too slow at 10^5.

Reference solution

Python

from typing import List

def shortestDistanceAfterQueries(n: int, queries: List[List[int]]) -> List[int]:
    nxt = list(range(1, n + 1))
    roads = n - 1
    ans = []
    for u, v in queries:
        if nxt[u] != -1 and nxt[u] < v:
            i = nxt[u]
            while i < v:
                j = nxt[i]
                nxt[i] = -1
                roads -= 1
                i = j
            nxt[u] = v
        ans.append(roads)
    return ans

Java

public static int[] shortestDistanceAfterQueries(int n, int[][] queries) {
    int[] nxt = new int[n];
    for (int i = 0; i < n; i++) nxt[i] = i + 1;
    int roads = n - 1;
    int[] ans = new int[queries.length];
    for (int k = 0; k < queries.length; k++) {
        int u = queries[k][0], v = queries[k][1];
        if (nxt[u] != -1 && nxt[u] < v) {
            int x = nxt[u];
            while (x < v) {
                int y = nxt[x];
                nxt[x] = -1;
                roads--;
                x = y;
            }
            nxt[u] = v;
        }
        ans[k] = roads;
    }
    return ans;
}

C++

vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {
    vector<int> nxt(n);
    for (int i = 0; i < n; i++) nxt[i] = i + 1;
    int roads = n - 1;
    vector<int> ans;
    for (auto& q : queries) {
        int u = q[0], v = q[1];
        if (nxt[u] != -1 && nxt[u] < v) {
            int x = nxt[u];
            while (x < v) {
                int y = nxt[x];
                nxt[x] = -1;
                roads--;
                x = y;
            }
            nxt[u] = v;
        }
        ans.push_back(roads);
    }
    return ans;
}

JavaScript

var shortestDistanceAfterQueries = function(n, queries) {
    var nxt = [];
    for (var i = 0; i < n; i++) nxt.push(i + 1);
    var roads = n - 1;
    var ans = [];
    for (var k = 0; k < queries.length; k++) {
        var u = queries[k][0], v = queries[k][1];
        if (nxt[u] !== -1 && nxt[u] < v) {
            var x = nxt[u];
            while (x < v) {
                var y = nxt[x];
                nxt[x] = -1;
                roads--;
                x = y;
            }
            nxt[u] = v;
        }
        ans.push(roads);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard