You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. The cities graph is not necessarily connected.
The score of a path between two cities is defined as the minimum distance of a road in this path.
Return the minimum possible score of a path between cities 1 and n.
Note:
1 and n multiple times along the path.1 and n.
Example 1:
Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]] Output: 5 Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5. It can be shown that no other path has less score.
Example 2:
Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]] Output: 2 Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.
Constraints:
2 <= n <= 1051 <= roads.length <= 105roads[i].length == 31 <= ai, bi <= nai != bi1 <= distancei <= 1041 and n.Problem Overview: You are given n cities connected by bidirectional roads with weights. The score of a path is defined as the minimum edge weight along that path. The goal is to find the minimum possible score of any path between city 1 and city n.
The key observation: since the graph is undirected and you can revisit cities, any path between two nodes in the same connected component can potentially include any edge in that component. That means the answer becomes the smallest edge weight in the connected component containing both city 1 and city n.
Approach 1: BFS / DFS Traversal (O(n + m) time, O(n + m) space)
Build an adjacency list for the graph and run a traversal starting from city 1. During traversal, visit all reachable cities and keep track of the minimum road weight encountered. Each time you iterate over neighbors, update the global minimum using min(ans, weight). Because all nodes reachable from city 1 belong to the same connected component, this traversal effectively scans every road that could appear in a valid path between city 1 and city n. This approach is straightforward and works well when you already represent the graph using adjacency lists.
Both Breadth-First Search and Depth-First Search work here. BFS uses a queue and explores level by level, while DFS uses recursion or a stack. Since the goal is simply to explore the connected component, either traversal produces the same result.
Approach 2: Union-Find (Disjoint Set Union) (O(m α(n)) time, O(n) space)
Use the Union-Find data structure to group cities into connected components. Iterate through all roads and union their endpoints. After building the sets, identify the root of city 1. Then iterate over all roads again and check whether both endpoints belong to this component. For every such road, update the minimum edge weight. The smallest weight among these roads becomes the path score.
This approach works because Union-Find quickly determines whether two nodes belong to the same component. With path compression and union by rank, each operation runs in nearly constant time O(α(n)).
Recommended for interviews: BFS or DFS traversal is usually the fastest to explain and implement during interviews. It directly explores the connected component of city 1 and tracks the smallest edge weight in O(n + m) time. Union-Find demonstrates stronger knowledge of graph connectivity structures and scales well when you repeatedly query components. Showing the traversal first proves understanding of graph connectivity, while the Union-Find optimization highlights deeper problem-solving skills.
This approach involves using the Union-Find data structure (also known as Disjoint Set Union, DSU) to manage connections between cities efficiently. By iterating over all roads, we determine which cities are interconnected. The key is to keep track of the minimum weight of a road that connects these cities after they are all unified.
This solution utilizes an efficient means of finding and unifying elements, reducing the overhead of nested loops and allowing operations near constant-time with path compression and union by rank techniques.
This solution uses a Disjoint Set Union (DSU) to identify all the cities that are connected together. It then iterates over the connections (roads), linking them up, and finally examines the edges to find the smallest possible score afterward.
Time Complexity: O(E log* V)
Space Complexity: O(V)
Another intuitive approach is to use graph traversal techniques such as BFS or DFS. Starting from city 1, you can explore all reachable cities while dynamically updating the minimum edge encountered during the exploration. This ensures you calculate the smallest score path by evaluating all potential paths to the destination city.
This C code uses DFS with an array of lists to store adjacent nodes. During DFS traversal, it keeps track of the minimum-weight edge to ensure the minimum score path is calculated.
Time Complexity: O(V + E)
Space Complexity: O(V + E)
According to the problem description, each edge can be passed multiple times, and it is guaranteed that node 1 and node n are in the same connected component. Therefore, the problem is actually looking for the smallest edge in the connected component where node 1 is located. We can use DFS, start searching from node 1, and find the smallest edge.
The time complexity is O(n + m), where n and m are the number of nodes and edges, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
We can also use BFS to solve this problem.
The time complexity is O(n + m), where n and m are the number of nodes and edges, respectively.
| Approach | Complexity |
|---|---|
| Using Union-Find Data Structure | Time Complexity: O(E log* V) |
| BFS/DFS Traversal | Time Complexity: O(V + E) |
| DFS | — |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS Traversal | O(n + m) | O(n + m) | Best when using adjacency lists and exploring connected components |
| DFS Traversal | O(n + m) | O(n + m) | Good for recursive exploration of graph components |
| Union-Find (Disjoint Set) | O(m α(n)) | O(n) | Useful when tracking connectivity across many edges or repeated component checks |
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python • NeetCodeIO • 13,899 views views
Watch 9 more video solutions →Practice Minimum Score of a Path Between Two Cities with our built-in code editor and test cases.
Practice on FleetCode