Watch 10 video solutions for Minimum Score of a Path Between Two Cities, a medium level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by NeetCodeIO has 13,899 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |