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.

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 firsti + 1 queries.

Examples

Example 1:

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

graph LR;
0 --> 1 --> 2 --> 3 --> 4
2 --> 4

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

graph LR;
0 --> 1 --> 2 --> 3 --> 4
0 --> 2
2 --> 4

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

%%{init: {'flowchart' : {'curve' : 'linear'}}}%%

flowchart-elk LR
 0 --> 1 --> 2 --> 3 --> 4
 0 --> 2
 2 --> 4
 0 --> 4

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:

graph LR;
0 --> 1 --> 2 --> 3
0 --> 3

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

flowchart-elk LR;
0 --> 1 --> 2 --> 3
0 --> 3
0 --> 2

After the addition of the road from 0 to 2, the length of the shortest path remains 1.

Constraints:

  • 3 <= n <= 500
  • 1 <= queries.length <= 500
  • 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.

Solution

Method 1 - Using BFS

The core idea is to maintain the shortest path length from city 0 to city n-1 as we continuously add new roads specified by the queries. Note that initially, the shortest path is the direct path from 0 to n-1 which is of length n-1.

  • Initial Setup: The cities are connected in a linear fashion from 0 to n-1, so the initial shortest path is the direct route which is of length n-1.
  • Applying Queries: For each query [ui, vi], we add the new road from city ui to city vi and then determine if this reduces the shortest path from 0 to n-1.
  • Shortest Path Calculation: Use a Breadth-First Search (BFS) or Dijkstra’s algorithm to dynamically find the shortest path after each query is applied.

Code

Java

class Solution {
    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        // Create an adjacency list for the graph
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
            if (i < n - 1) graph[i].add(new int[]{i + 1, 1});
        }

        // Result array to store the shortest path lengths after each query
        int[] ans = new int[queries.length];

        // Process each query
        for (int i = 0; i < queries.length; i++) {
            // Add the new road
            graph[queries[i][0]].add(new int[]{queries[i][1], 1});

            // Find the shortest path from 0 to n-1 using BFS or Dijkstra
            ans[i] = bfs(0, n - 1, graph, n);
        }

        return ans;
    }

    // BFS based method to find the shortest path from start to end
    private int bfs(int start, int end, List<int[]>[] graph, int n) {
        Queue<int[]> q = new LinkedList<>();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        q.offer(new int[]{start, 0});

        while (!q.isEmpty()) {
            int[] node = q.poll();
            int u = node[0], d = node[1];

            for (int[] adj : graph[u]) {
                int v = adj[0];
                if (d + 1 < dist[v]) {
                    dist[v] = d + 1;
                    q.offer(new int[]{v, d + 1});
                }
            }
        }

        return dist[end];
    }
}
Python
class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        graph = [[] for _ in range(n)]
        for i in range(n - 1):
            graph[i].append((i + 1, 1))
        ans: List[int] = []
        for ui, vi in queries:
            graph[ui].append((vi, 1))
            ans.append(self.bfs(0, n - 1, graph, n))
        return ans

    def bfs(self, start: int, end: int, graph: List[List[Tuple[int, int]]], n: int) -> int:
        q: Deque[Tuple[int, int]] = deque([(start, 0)])
        dist: List[int] = [float('inf')] * n
        dist[start] = 0
        while q:
            u, d = q.popleft()
            for v, _ in graph[u]:
                if d + 1 < dist[v]:
                    dist[v] = d + 1
                    q.append((v, d + 1))
        return dist[end]

Complexity

  • ⏰ Time complexity: The BFS or Dijkstra’s algorithm used to find the shortest path will take O(V + E) where V is the number of cities and E is the number of roads (including the new roads added). Given q queries, the overall complexity would be O(q * (V + E)).
  • 🧺 Space complexity: The space required by the BFS/Dijkstra’s algorithm includes the space for the graph representation and the data structures used in BFS/Dijkstra, giving a total of O(V + E) space.