Minimum Score of a Path Between Two Cities — Solution
Minimum Score of a Path Between Two Cities solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Score of a Path Between Two Cities is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Oracle interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph, Union Find
- Asked at: Amazon, Google, Oracle
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
n cities numbered 1 … n are joined by bidirectional roads; roads[i] = [a, b, distance].
The score of a path is the minimum distance among the roads it uses. A path may revisit cities and reuse roads, and need not be the shortest. Return the minimum possible score of any path from city 1 to city n. City n is reachable from city 1.
Example 1
Input: roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]], n = 4
Output: 5
Explanation: Walk 1 → 2 → 4 → 2 → 4: the road of length 5 is on the path.
Example 2
Input: roads = [[1,2,2],[1,3,4],[3,4,7]], n = 4
Output: 2
Explanation: Detour over the road of length 2 and come back.
Example 3
Input: roads = [[1,2,3]], n = 2
Output: 3
Constraints
2 <= n <= 10^51 <= roads.length <= 10^5roads[i].length == 31 <= a, b <= na != b1 <= distance <= 10^4There are no repeated edges.City n is reachable from city 1.
Hints for Minimum Score of a Path Between Two Cities
Hint 1
A path may wander freely and reuse roads, so it can take in any road in the connected component it starts from.
Hint 2
So the shape of the path is irrelevant — only which roads are reachable.
Hint 3
Find the component holding city 1 and return the smallest road weight inside it.
How to solve Minimum Score of a Path Between Two Cities
Because a path can revisit cities and reuse roads, it can detour to any road in city 1's connected component and come back. So the answer is simply the minimum weight among the component's roads.
Approach
- Union the endpoints of every road.
- Find the component root of city 1 — city
nis in it by assumption. - Scan the roads and take the minimum weight among those inside that component.
Why it works
This is why no shortest-path algorithm appears: the usual trade-off between path length and edge weights vanishes once revisiting is free. Detouring along the component's lightest road, then walking on to city n, gives a path whose minimum is that weight — and no path can beat it, since every road it uses lies in the component.
Complexity
- Time —
O(n + m · α(n)) - Space —
O(n)
Pitfalls
- Dijkstra's algorithm answers a different question and gives the wrong result here.
- Roads outside city 1's component must be ignored, however light.
- Cities are numbered from 1, so size the union-find arrays accordingly.
Reference solution
Python
from typing import List
def minScore(n: int, roads: List[List[int]]) -> int:
parent = list(range(n + 1))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for a, b, _ in roads:
ra, rb = find(a), find(b)
if ra != rb:
parent[rb] = ra
root = find(1)
return min(d for a, _, d in roads if find(a) == root)Java
private static int[] msParent;
private static int msFind(int x) {
while (msParent[x] != x) {
msParent[x] = msParent[msParent[x]];
x = msParent[x];
}
return x;
}
public static int minScore(int n, int[][] roads) {
msParent = new int[n + 1];
for (int i = 0; i <= n; i++) msParent[i] = i;
for (int[] r : roads) {
int a = msFind(r[0]), b = msFind(r[1]);
if (a != b) msParent[b] = a;
}
int root = msFind(1);
int best = Integer.MAX_VALUE;
for (int[] r : roads) {
if (msFind(r[0]) != root) continue;
best = Math.min(best, r[2]);
}
return best;
}C++
int minScore(int n, vector<vector<int>>& roads) {
vector<int> parent(n + 1);
for (int i = 0; i <= n; i++) parent[i] = i;
function<int(int)> find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (auto& r : roads) {
int a = find(r[0]), b = find(r[1]);
if (a != b) parent[b] = a;
}
int root = find(1);
int best = INT_MAX;
for (auto& r : roads) {
if (find(r[0]) != root) continue;
best = min(best, r[2]);
}
return best;
}JavaScript
var minScore = function(n, roads) {
var i;
var parent = [];
for (i = 0; i <= n; i++) parent.push(i);
var find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
for (i = 0; i < roads.length; i++) {
var a = find(roads[i][0]), b = find(roads[i][1]);
if (a !== b) parent[b] = a;
}
var root = find(1);
var best = 1000000000;
for (i = 0; i < roads.length; i++) {
if (find(roads[i][0]) !== root) continue;
if (roads[i][2] < best) best = roads[i][2];
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)