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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


Input: n = 5, queries = [[2,4],[0,2],[0,4]]

Output: [3,2,1]

Explanation:

![](https://assets.leetcode.com/uploads/2024/06/28/image8.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.leetcode.com/uploads/2024/06/28/image9.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.leetcode.com/uploads/2024/06/28/image10.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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Input: n = 4, queries = [[0,3],[0,2]]

Output: [1,1]

Explanation:

![](https://assets.leetcode.com/uploads/2024/06/28/image11.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.leetcode.com/uploads/2024/06/28/image12.jpg)

After the addition of the road from 0 to 2, the length of the shortest path
remains 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]
  • 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].

Solution

Method 1 – Greedy with Path Shortcutting

Intuition

The shortest path from city 0 to city n-1 is initially n-1 (the direct chain). Each query adds a shortcut (ui, vi), which can only reduce the path if it creates a shorter jump. Since queries never overlap in a nested way, we can greedily keep track of the shortest jump to n-1.

Approach

  1. Start with the initial shortest path as n-1 (the direct chain).
  2. For each query [u, v]:
    • The shortcut from u to v allows us to go from 0 to u (u steps), then jump to v, then go to n-1 (n-1-v steps).
    • The total path is u + 1 + (n-1-v).
    • Update the shortest path if this is smaller.
  3. After each query, record the current shortest path.
  4. Return the list of shortest paths after each query.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> shortestPath(int n, vector<vector<int>>& queries) {
        int ans = n - 1;
        vector<int> res;
        for (auto& q : queries) {
            int u = q[0], v = q[1];
            ans = min(ans, u + 1 + (n - 1 - v));
            res.push_back(ans);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func shortestPath(n int, queries [][]int) []int {
    ans := n - 1
    res := make([]int, 0, len(queries))
    for _, q := range queries {
        u, v := q[0], q[1]
        if u+1+(n-1-v) < ans {
            ans = u+1+(n-1-v)
        }
        res = append(res, ans)
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public List<Integer> shortestPath(int n, List<List<Integer>> queries) {
        int ans = n - 1;
        List<Integer> res = new ArrayList<>();
        for (List<Integer> q : queries) {
            int u = q.get(0), v = q.get(1);
            ans = Math.min(ans, u + 1 + (n - 1 - v));
            res.add(ans);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun shortestPath(n: Int, queries: List<List<Int>>): List<Int> {
        var ans = n - 1
        val res = mutableListOf<Int>()
        for (q in queries) {
            val u = q[0]
            val v = q[1]
            ans = minOf(ans, u + 1 + (n - 1 - v))
            res.add(ans)
        }
        return res
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def shortestPath(self, n: int, queries: list[list[int]]) -> list[int]:
        ans = n - 1
        res: list[int] = []
        for u, v in queries:
            ans = min(ans, u + 1 + (n - 1 - v))
            res.append(ans)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn shortest_path(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let mut ans = n - 1;
        let mut res = Vec::with_capacity(queries.len());
        for q in queries {
            let u = q[0];
            let v = q[1];
            ans = ans.min(u + 1 + (n - 1 - v));
            res.push(ans);
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    shortestPath(n: number, queries: number[][]): number[] {
        let ans = n - 1;
        const res: number[] = [];
        for (const [u, v] of queries) {
            ans = Math.min(ans, u + 1 + (n - 1 - v));
            res.push(ans);
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(q) where q = number of queries. For each query, we do constant time work (min, arithmetic, push).
  • 🧺 Space complexity: O(q) for the result array, as we store one answer per query.