Skip to main content
Talentd

Shortest Distance After Road Addition Queries I - Solution & Explanation

MediumArrayBreadth-First SearchGraph13 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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 <= 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.

Approach Overview

Problem Overview: You start with n cities connected in a straight line where each city i has a road to i+1. Queries add new directed roads between cities. After each addition, compute the shortest distance from city 0 to city n-1.

Approach 1: Breadth-First Search (BFS) Recompute per Query (Time: O(q*(n+e)), Space: O(n+e))

Maintain an adjacency list representing the current graph. Initially add edges i → i+1 for all cities. For every query (u, v), append the new edge to the adjacency list and run a Breadth-First Search starting from node 0. Since all roads have equal weight, BFS naturally finds the shortest number of edges to each city. The first time you reach n-1 gives the shortest path length. This approach is straightforward and works well because constraints keep the graph relatively small. Each query triggers a fresh traversal of the graph.

Approach 2: Dijkstra with Priority Queue (Time: O(q*(n+e) log n), Space: O(n+e))

Another option is running Dijkstra's Algorithm after each road insertion. Store the graph in an adjacency list and use a min-heap to always expand the node with the smallest current distance. Although all edges have weight 1 (making BFS slightly more efficient), Dijkstra provides a general solution for shortest paths and works even if weights change in future variations. After each query, push the start node 0 into the priority queue and relax edges until reaching n-1. The priority queue ensures nodes are processed in increasing distance order.

Recommended for interviews: BFS is typically expected because every road has equal weight. Running BFS after each query demonstrates understanding of shortest paths in unweighted graphs and keeps implementation simple. Mentioning the Dijkstra alternative shows awareness of weighted graph techniques and broader problem-solving skills.

Approach 1: Breadth-First Search (BFS) Approach

This approach treats the problem as a graph traversal problem where each city is a node and roads are directed edges. Initially, the graph is linear, and each query introduces a single directed edge. We can use BFS to update and find the shortest path after each new road is added, recalculating the shortest path from node 0 to node n-1.

This Python function shortest_path accepts the number of cities, n, and the list of queries that represent new road additions. The function maintains a dynamic graph representation and repeatedly performs BFS to determine the new shortest path from city 0 to city n-1 after each query.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * q), where n is the number of cities and q is the number of queries, due to the BFS traversal for each query.
Space Complexity: O(n + q), accounting for graph representation and BFS queue.

Try this approach in the editor →

Approach 2: Dijkstra's Algorithm with Priority Queue

This approach models the problem as a weighted graph and uses Dijkstra's algorithm, which is suitable since the graph predominantly has unit weights. This algorithm efficiently finds the shortest path from the start city to the end city after each new road is introduced, leveraging a priority queue to always expand the shortest known total distance path.

This C++ implementation of Dijkstra's algorithm uses a priority queue to determine the shortest path efficiently. Initially, the graph is set up with each city i and i+1 connected. For each query, a new edge is added, and the Dijkstra's algorithm recalculates the shortest path.

Code

C++Java

C++

Java

Complexity

Time Complexity: O((n + q) log n), due to the priority queue operations within Dijkstra’s algorithm for each query.
Space Complexity: O(n + q), needed for graph representation and distance calculations.

Try this approach in the editor →

Approach 3: BFS

We first build a directed graph g, where g[i] represents the list of cities that can be reached from city i. Initially, each city i has a one-way road to city i + 1.

Then, for each query [u, v], we add v to the list of reachable cities from u, and then use BFS to find the shortest path length from city 0 to city n - 1, adding the result to the answer array.

Finally, we return the answer array.

The time complexity is O(q times (n + q)), and the space complexity is O(n + q). Here, n and q are the number of cities and the number of queries, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS) Approach

Time Complexity: O(n * q), where n is the number of cities and q is the number of queries, due to the BFS traversal for each query.
Space Complexity: O(n + q), accounting for graph representation and BFS queue.

Dijkstra's Algorithm with Priority Queue

Time Complexity: O((n + q) log n), due to the priority queue operations within Dijkstra’s algorithm for each query.
Space Complexity: O(n + q), needed for graph representation and distance calculations.

BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search per QueryO(q*(n+e))O(n+e)Best for unweighted graphs where each road has equal cost
Dijkstra with Priority QueueO(q*(n+e) log n)O(n+e)General shortest-path solution or when edge weights vary

Video Solution

Shortest Distance After Road Addition Queries I | Easy Explanation | Leetcode 3243 |codestorywithMIK • codestorywithMIK • 7,480 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Shortest Distance After Road Addition Queries I easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 61%. The main challenge is recognizing that the graph changes after each query and recomputing the shortest path efficiently using BFS or Dijkstra.
Shortest Distance After Road Addition Queries I Python/Java solution
Python and JavaScript implementations typically use BFS with a queue because the graph is unweighted. C++ and Java solutions sometimes demonstrate Dijkstra with a priority queue. Both approaches compute the shortest path from node 0 to node n-1 after each query.
How to solve Shortest Distance After Road Addition Queries I efficiently?
Maintain an adjacency list of the graph and append the new road for every query. After inserting the edge, run BFS from node 0 to compute the distance to node n-1. Because all edges have weight 1, BFS guarantees the optimal path length without needing a priority queue.
What is the best approach for Shortest Distance After Road Addition Queries I?
Breadth-First Search (BFS) after each query is the most practical solution. Since every road has weight 1, BFS naturally finds the shortest number of edges from city 0 to city n-1. Each query adds one edge to the graph, then a BFS traversal computes the updated shortest path.
Is Shortest Distance After Road Addition Queries I asked at Google/Amazon/Meta?
Graph traversal and shortest path problems are common in interviews at companies like Google, Amazon, and Meta. Variations involving BFS, dynamic edge updates, or shortest path recomputation frequently appear in online assessments and technical rounds.
What data structure is used in Shortest Distance After Road Addition Queries I?
The solution relies on an adjacency list to represent the graph and a queue for BFS traversal. If using Dijkstra, a priority queue (min-heap) is also required. Arrays or lists track visited nodes and current distances.
What is the time complexity of Shortest Distance After Road Addition Queries I?
The BFS approach runs in O(q*(n+e)) time where q is the number of queries, n is the number of cities, and e is the number of roads currently in the graph. Each query triggers a full BFS traversal. Space complexity is O(n+e) for storing the adjacency list and visited structures.

Ready to solve this problem?

Practice Shortest Distance After Road Addition Queries I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays