LeetCode in Kotlin
3243. Shortest Distance After Road Addition Queries I
Medium
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]
Explanation:
After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.
After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.
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:
After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.
After the addition of the road from 0 to 2, the length of the shortest path remains 1.
Constraints:
3 <= n <= 5001 <= queries.length <= 500queries[i].length == 20 <= queries[i][0] < queries[i][1] < n1 < queries[i][1] - queries[i][0]- There are no repeated roads among the queries.
Solution
class Solution {
fun shortestDistanceAfterQueries(n: Int, queries: Array<IntArray>): IntArray {
val dist = IntArray(n)
for (i in 0 until n) {
dist[i] = i
}
val parent: Array<ArrayList<Int>> = Array(n) { ArrayList() }
for (i in 0 until n) {
parent[i] = ArrayList()
if (i != n - 1) {
parent[i].add(i + 1)
}
}
val ans = IntArray(queries.size)
for (i in queries.indices) {
val u = queries[i][0]
val v = queries[i][1]
if (dist[v] > dist[u] + 1) {
dist[v] = dist[u] + 1
parent[u].add(v)
updateDistance(v, dist, parent)
} else {
parent[u].add(v)
}
ans[i] = dist[n - 1]
}
return ans
}
fun updateDistance(par: Int, dist: IntArray, parent: Array<ArrayList<Int>>) {
for (i in parent[par].indices) {
val child = parent[par][i]
if (dist[child] > dist[par] + 1) {
dist[child] = dist[par] + 1
updateDistance(child, dist, parent)
}
}
}
}