Shortest Distance After Road Addition Queries I
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 first i + 1 queries.
Example 1
Input
n = 5, queries = [[2,4],[0,2],[0,4]]Output
[3,2,1]After adding roads from 2 to 4, then 0 to 2, then 0 to 4, the shortest path lengths from 0 to 4 are 3, 2, and 1 respectively.
Example 2
Input
n = 4, queries = [[0,3],[0,2]]Output
[1,1]After adding the road from 0 to 3, the shortest path length is 1, and adding the road from 0 to 2 does not reduce it further.
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.
Asked at 3 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.