Skip to main content
Talentd

Shortest Distance After Road Addition Queries II - Solution & Explanation

HardArrayGreedyGraphOrdered Set14 min read
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.

There are no two queries such that queries[i][0] < queries[j][0] < queries[i][1] < queries[j][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 <= 105
  • 1 <= queries.length <= 105
  • 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.
  • There are no two queries such that i != j and queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1].

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 (u, v). After every addition, compute the shortest distance from city 0 to city n-1. The challenge is updating the shortest path efficiently as the graph changes repeatedly.

Approach 1: Dynamic Path Update with BFS (Time: O(q * (n + e)), Space: O(n + e))

Treat the cities and roads as a directed graph. Maintain an adjacency list that initially contains edges i → i+1. For each query, insert the new edge u → v and run a BFS from node 0 to recompute the shortest distance to n-1. BFS works because every edge has equal weight, so the first time you reach a node you have the optimal distance. This approach is simple and reliable but recomputes the path from scratch after every update, which becomes expensive when q grows.

Approach 2: Graph Updates with DJ-Set (Union-Find) (Time: ~O(n + q α(n)), Space: O(n))

The key observation: the original path is linear and queries only add forward edges u < v. When a shortcut u → v appears, the intermediate nodes between them may no longer contribute to the shortest path. Use a disjoint-set structure to "skip" nodes that become redundant. Maintain a next-pointer style structure (similar to an ordered set) where union operations compress consecutive nodes already bypassed by shortcuts. Each query effectively removes edges along the linear chain that are now unnecessary, decreasing the total path length. Path compression keeps operations nearly constant time, so across all queries the total work stays close to linear.

Recommended for interviews: Start with the BFS recomputation approach. It clearly models the dynamic graph and shows you understand shortest-path traversal. Then explain the observation that queries only add forward shortcuts and the base graph is linear. The Union-Find compression method leverages that structure to avoid recomputing BFS, reducing the complexity to near O(n + q). Interviewers usually expect recognition of this structural optimization rather than repeated graph traversal.

Approach 1: Dynamic Path Update with BFS

This approach utilizes BFS to update and compute the shortest path length from city 0 to city n-1 after each road addition. The BFS ensures that we efficiently manage path updates by traversing the shortest possible paths and updating distances as we encounter new shortcuts.

The Python solution employs a Breadth-First Search (BFS) to determine the shortest path length from city 0 to city n-1 after each new road is added. We maintain an adjacency list to represent the directed graph. For each query, we add the new road to the adjacency list and then use BFS to find the shortest path distance. This distance is collected and returned as the result.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(q * (n + E)), where q is the number of queries and E is the number of edges. Space Complexity: O(n + E) due to the adjacency list and distance tracking.

Try this approach in the editor →

Approach 2: Graph Updates with DJ-Set (Union-Find)

This approach uses a Disjoint Set Union (DSU), also known as Union-Find, to manage the connectivity between nodes (cities). We explore each query and attempt to track connected components to adjust and check path lengths from city 0 to city n-1.

The C++ solution uses a disjoint set data structure to manage the connected components of the graph. With each query, it attempts to unite the specified cities and checks if city 0 and city n-1 belong to the same connected component. If they are connected, it adds '1' to the result, otherwise, it calculates the additional path cost.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(q * α(n)), where q is the number of queries and α is the Inverse Ackermann function. Space Complexity: O(n) for the DSU structure.

Try this approach in the editor →

Approach 3: Greedy + Recording Jump Positions

We define an array nxt of length n - 1, where nxt[i] represents the next city that can be reached from city i. Initially, nxt[i] = i + 1.

For each query [u, v], if u' and v' have already been connected before, and u' leq u < v leq v', then we can skip this query. Otherwise, we need to set the next city number for cities from nxt[u] to nxt[v - 1] to 0, and set nxt[u] to v.

During this process, we maintain a variable cnt, which represents the length of the shortest path from city 0 to city n - 1. Initially, cnt = n - 1. Each time we set the next city number for cities in [nxt[u], v) to 0, cnt decreases by 1.

Time complexity is O(n + q), and space complexity is O(n). 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
Dynamic Path Update with BFS

Time Complexity: O(q * (n + E)), where q is the number of queries and E is the number of edges. Space Complexity: O(n + E) due to the adjacency list and distance tracking.

Graph Updates with DJ-Set (Union-Find)

Time Complexity: O(q * α(n)), where q is the number of queries and α is the Inverse Ackermann function. Space Complexity: O(n) for the DSU structure.

Greedy + Recording Jump Positions—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Graph BFS After Each QueryO(q * (n + e))O(n + e)Good baseline approach when constraints are small or for explaining shortest-path logic in interviews
Union-Find Graph CompressionO(n + q α(n))O(n)Optimal solution when many queries are present and the graph structure is mostly linear

Video Solution

A-C | Leetcode Weekly Contest 409 Editorials | Shortest Distance After Road Addition Queries • Abhinav Awasthi • 3,917 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Shortest Distance After Road Addition Queries II easy or hard?
LeetCode classifies this problem as Hard because it combines graph traversal, incremental updates, and structural optimization. The naive BFS solution is easy to implement, but recognizing the union-find compression trick that achieves near-linear complexity requires deeper insight.
Shortest Distance After Road Addition Queries II Python/Java solution
Python and Java implementations often start with the BFS recomputation approach using adjacency lists and a queue. Optimized implementations maintain a Union-Find structure with path compression to skip nodes already bypassed by shortcuts, significantly reducing the total number of operations.
How to solve Shortest Distance After Road Addition Queries II in O(n + q)?
Use a disjoint-set structure to track which nodes along the original chain are still part of the active shortest path. When a query adds a shortcut edge (u, v), union operations skip intermediate nodes between them so they are processed only once overall. Path compression ensures each node is removed from consideration at most once, leading to near O(n + q) total work.
What is the best approach for Shortest Distance After Road Addition Queries II?
The most efficient approach uses a Union-Find (disjoint set) structure to compress segments of the original linear path that become unnecessary after shortcut edges are added. Since queries only add forward edges, nodes between u and v can be skipped once a shortcut appears. With path compression, the total complexity becomes roughly O(n + q α(n)), which is close to linear.
Is Shortest Distance After Road Addition Queries II asked at Google/Amazon/Meta?
Problems involving dynamic shortest paths, union-find optimizations, and incremental graph updates appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of this problem test whether you can recognize structural constraints in a graph and avoid recomputing BFS or Dijkstra repeatedly.
What data structure is used in Shortest Distance After Road Addition Queries II?
Common implementations combine adjacency lists for the graph representation with BFS for the baseline approach. The optimized solution uses a disjoint-set (Union-Find) structure together with pointer skipping techniques similar to an ordered set to efficiently remove redundant nodes from the linear path.
What is the time complexity of Shortest Distance After Road Addition Queries II?
A straightforward BFS recomputation after each query takes O(q * (n + e)) time because the graph traversal runs every time a road is added. The optimized Union-Find compression approach reduces the total work to about O(n + q α(n)), where α(n) is the inverse Ackermann function and behaves almost like a constant in practice.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays