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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(V + E)
Space Complexity: O(V + E)
| Approach | Complexity |
|---|---|
| Using Union-Find Data Structure | Time Complexity: O(E log* V) |
| BFS/DFS Traversal | Time Complexity: O(V + E) |
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python • NeetCodeIO • 11,576 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