Shortest Distance After Road Addition Queries

Tested Python solution for LeetCode 3243 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 3243, Medium. Topics: Array, Breadth-First Search, Graph Theory. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 22 parametrized pytest cases, and a playground notebook:

lcpy gen -n 3243   # by problem number
lcpy gen -s shortest_distance_after_queries_i   # by problem name

​

Problem

You are given an integer <code>n</code> and a 2D integer array <code>queries</code>.

There are <code>n</code> cities numbered from <code>0</code> to <code>n - 1</code>. Initially, there is a <strong>unidirectional</strong> road from city <code>i</code> to city <code>i + 1</code> for all <code>0 <= i < n - 1</code>.

<code>queries[i] = [u_i, v_i]</code> represents the addition of a new <strong>unidirectional</strong> road from city <code>u_i</code> to city <code>v_i</code>. After each query, you need to find the <strong>length</strong> of the <strong>shortest path</strong> from city <code>0</code> to city <code>n - 1</code>.

Return an array <code>answer</code> where for each <code>i</code> in the range <code>[0, queries.length - 1]</code>, <code>answer[i]</code> is the length of the shortest path from city <code>0</code> to city <code>n - 1</code> after processing the <strong>first</strong> <code>i + 1</code> queries.

​

Examples

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.

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

• <code>3 <= n <= 500</code>
• <code>1 <= queries.length <= 500</code>
• <code>queries[i].length == 2</code>
• <code>0 <= queries[i][0] < queries[i][1] < n</code>
• <code>1 < queries[i][1] - queries[i][0]</code>
• There are no repeated roads among the queries.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class Solution:
    # Time: O(n + q * k) where k is the number of distance decreases, q = len(queries)
    # Space: O(n + q)
    def shortest_distance_after_queries(self, n: int, queries: list[list[int]]) -> list[int]:
        adj: list[list[int]] = [[i + 1] for i in range(n - 1)]
        adj.append([])
        dist = list(range(n))
        result: list[int] = []

        for u, v in queries:
            adj[u].append(v)
            if dist[u] + 1 >= dist[v]:
                result.append(dist[n - 1])
                continue

            dist[v] = dist[u] + 1
            queue: deque[int] = deque([v])
            while queue:
                cur = queue.popleft()
                for nxt in adj[cur]:
                    if dist[cur] + 1 < dist[nxt]:
                        dist[nxt] = dist[cur] + 1
                        queue.append(nxt)
            result.append(dist[n - 1])

        return result

​

Complexity

Time	Space
O(n + q * k) where k is the number of distance decreases, q = len(queries)	O(n + q)

​

Tags

NeetCode All.