Minimum Score of a Path Between Two Cities solution and explanation
Google
9 more videos on this problem
Minimum Score of a Path Between Two Cities - Leetcode 2492 - PythonNeetCodeIO · 7:48 · 15K views
Minimum Score of a Path Between Two Cities | Leetcode - 2492 | GOOGLE | codestorywithMIKcodestorywithMIK · 14:45 · 12K views
2492 || Minimum Score of a Path Between Two Cities || C++ || Leetcode Daily ChallengeCodeFreaks · 18:55 · 883 views
Minimum Score of a Path Between Two Cities - Leetcode 2492 - PythonTechError · 11:45 · 711 views
2492. Minimum Score of a Path Between Two Cities (Leetcode Medium)Programming Live with Larry · 12:08 · 701 views
2492. Minimum Score of a Path Between Two Cities - JAVA (DFS / BFS on Graph - Detailed explanation)Sourin Majumdar · 11:44 · 400 views
2492. Minimum Score of a Path Between Two Cities | Leetcode Daily - PythonLeetcode Daily · 5:31 · 283 views
2492. Minimum Score of a Path Between Two Cities | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 9:55 · 281 views
Leetcode 2492: Minimum Score of a Path Between Two CitiesAlgorithms Casts · 13:27 · 257 views
Minimum Score of a Path Between Two Cities | LeetCode 2492 - Pythonimpoldev · 7:23 · 144 views
The problem
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:
- A path is a sequence of roads between two cities.
- It is allowed for a path to contain the same road multiple times, and you can visit cities
1andnmultiple times along the path. - The test cases are generated such that there is at least one path between
1andn.
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 <= 104- There are no repeated edges.
- There is at least one path between
1andn.
Approach overview
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 1: Using Union-Find Data Structure
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.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n + 1))
self.rank = [0] * (n + 1)
def find(self, u):
if self.parent[u] != u:
self.parent[u] = self.find(self.parent[u])
return self.parent[u]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu != pv:
if self.rank[pu] > self.rank[pv]:
self.parent[pv] = pu
elif self.rank[pu] < self.rank[pv]:
self.parent[pu] = pv
else:
self.parent[pv] = pu
self.rank[pu] += 1
def minScore(n, roads):
uf = UnionFind(n)
result = float('inf')
for a, b, dist in roads:
uf.union(a, b)
for a, b, dist in roads:
if uf.find(a) == uf.find(1) or uf.find(b) == uf.find(1):
result = min(result, dist)
return resultimport java.util.*;
class Solution {
class UnionFind {
int[] parent, rank;
UnionFind(int n) {
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 1; i <= n; i++)
parent[i] = i;
}
int find(int u) {
if (parent[u] != u)
parent[u] = find(parent[u]);
return parent[u];
}
void union(int u, int v) {
int pu = find(u);
int pv = find(v);
if (pu != pv) {
if (rank[pu] > rank[pv])
parent[pv] = pu;
else if (rank[pu] < rank[pv])
parent[pu] = pv;
else {
parent[pv] = pu;
rank[pu]++;
}
}
}
}
public int minScore(int n, int[][] roads) {
UnionFind uf = new UnionFind(n);
int result = Integer.MAX_VALUE;
for (int[] road : roads) {
int a = road[0], b = road[1];
uf.union(a, b);
}
for (int[] road : roads) {
if (uf.find(road[0]) == uf.find(1) || uf.find(road[1]) == uf.find(1))
result = Math.min(result, road[2]);
}
return result;
}
}#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
class UnionFind {
public:
vector<int> parent, rank;
UnionFind(int n) {
parent.resize(n + 1);
rank.resize(n + 1, 0);
for(int i = 1; i <= n; i++)
parent[i] = i;
}
int find(int u) {
if(parent[u] != u)
parent[u] = find(parent[u]);
return parent[u];
}
void merge(int u, int v) {
int pu = find(u);
int pv = find(v);
if(pu != pv) {
if(rank[pu] > rank[pv])
parent[pv] = pu;
else if(rank[pu] < rank[pv])
parent[pu] = pv;
else {
parent[pv] = pu;
rank[pu]++;
}
}
}
};
int minScore(int n, vector<vector<int>>& roads) {
UnionFind uf(n);
int minDistance = INT_MAX;
for (auto& road : roads) {
uf.merge(road[0], road[1]);
}
int root1 = uf.find(1);
for (auto& road : roads) {
if (uf.find(road[0]) == root1 || uf.find(road[1]) == root1)
minDistance = min(minDistance, road[2]);
}
return minDistance;
}class UnionFind {
constructor(n) {
this.parent = Array.from({length: n + 1}, (_, i) => i);
this.rank = Array(n + 1).fill(0);
}
find(u) {
if (this.parent[u] !== u) {
this.parent[u] = this.find(this.parent[u]);
}
return this.parent[u];
}
union(u, v) {
let pu = this.find(u);
let pv = this.find(v);
if (pu !== pv) {
if (this.rank[pu] > this.rank[pv]) {
this.parent[pv] = pu;
} else if (this.rank[pu] < this.rank[pv]) {
this.parent[pu] = pv;
} else {
this.parent[pv] = pu;
this.rank[pu]++;
}
}
}
}
function minScore(n, roads) {
const uf = new UnionFind(n);
let result = Infinity;
for (const [a, b, dist] of roads) {
uf.union(a, b);
}
for (const [a, b, dist] of roads) {
if (uf.find(a) === uf.find(1) || uf.find(b) === uf.find(1)) {
result = Math.min(result, dist);
}
}
return result;
}#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int find(int* parent, int i) {
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
}
void union_set(int* parent, int* rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
int minScore(int n, int** roads, int roadsSize, int* roadsColSize) {
int* parent = (int*)malloc((n + 1) * sizeof(int));
int* rank = (int*)calloc(n + 1, sizeof(int));
for (int i = 1; i <= n; i++)
parent[i] = i;
int minDistance = INT_MAX;
for (int i = 0; i < roadsSize; i++) {
int a = roads[i][0];
int b = roads[i][1];
int dist = roads[i][2];
union_set(parent, rank, a, b);
}
int root1 = find(parent, 1);
int rootN = find(parent, n);
for (int i = 0; i < roadsSize; i++) {
int a = roads[i][0];
int b = roads[i][1];
int dist = roads[i][2];
if (find(parent, a) == root1 || find(parent, b) == root1)
if (dist < minDistance)
minDistance = dist;
}
free(parent);
free(rank);
return minDistance;
}public class Solution {
public class UnionFind {
public int[] parent, rank;
public UnionFind(int n) {
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 1; i <= n; i++)
parent[i] = i;
}
public int Find(int u) {
if (parent[u] != u)
parent[u] = Find(parent[u]);
return parent[u];
}
public void Union(int u, int v) {
int pu = Find(u);
int pv = Find(v);
if (pu != pv) {
if (rank[pu] > rank[pv])
parent[pv] = pu;
else if (rank[pu] < rank[pv])
parent[pu] = pv;
else {
parent[pv] = pu;
rank[pu]++;
}
}
}
}
public int MinScore(int n, int[][] roads) {
UnionFind uf = new UnionFind(n);
int result = int.MaxValue;
foreach (int[] road in roads) {
uf.Union(road[0], road[1]);
}
foreach (int[] road in roads) {
if (uf.Find(road[0]) == uf.Find(1) || uf.Find(road[1]) == uf.Find(1))
result = Math.Min(result, road[2]);
}
return result;
}
}Python implementation leverages a Union-Find class to efficiently deal with interconnected components and keeps track of the minimal distance of roads connecting city 1 with other connected cities.
Time Complexity: O(E log* V)
Space Complexity: O(V)
Approach 2: BFS/DFS Traversal
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.
def minScore(n, roads):
from collections import defaultdict
graph = defaultdict(list)
for a, b, dist in roads:
graph[a].append((b, dist))
graph[b].append((a, dist))
def dfs(node, visited, currentMin):
visited[node] = True
for adj, dist in graph[node]:
if not visited[adj]:
currentMin = min(currentMin, dist)
currentMin = dfs(adj, visited, currentMin)
return currentMin
visited = [False] * (n + 1)
return dfs(1, visited, float('inf'))import java.util.*;
class Solution {
private int dfs(int node, boolean[] visited, Map<Integer, List<int[]>> graph, int currentMin) {
visited[node] = true;
for (int[] edge : graph.get(node)) {
int adj = edge[0];
int dist = edge[1];
if (!visited[adj]) {
currentMin = Math.min(currentMin, dist);
currentMin = dfs(adj, visited, graph, currentMin);
}
}
return currentMin;
}
public int minScore(int n, int[][] roads) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for (int i = 1; i <= n; i++)
graph.put(i, new ArrayList<>());
for (int[] road : roads) {
graph.get(road[0]).add(new int[]{road[1], road[2]});
graph.get(road[1]).add(new int[]{road[0], road[2]});
}
boolean[] visited = new boolean[n + 1];
return dfs(1, visited, graph, Integer.MAX_VALUE);
}
}#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int minScoreDFS(int node, vector<vector<pair<int, int>>>& graph, vector<bool>& visited, int currentMin) {
visited[node] = true;
for (auto& edge : graph[node]) {
int adj = edge.first;
int dist = edge.second;
if (!visited[adj]) {
currentMin = min(currentMin, dist);
currentMin = minScoreDFS(adj, graph, visited, currentMin);
}
}
return currentMin;
}
int minScore(int n, vector<vector<int>>& roads) {
vector<vector<pair<int, int>>> graph(n + 1);
for (auto& road : roads) {
graph[road[0]].emplace_back(road[1], road[2]);
graph[road[1]].emplace_back(road[0], road[2]);
}
vector<bool> visited(n + 1, false);
return minScoreDFS(1, graph, visited, INT_MAX);
}function minScore(n, roads) {
const graph = Array.from({ length: n + 1 }, () => []);
for (const [a, b, dist] of roads) {
graph[a].push([b, dist]);
graph[b].push([a, dist]);
}
const visited = new Array(n + 1).fill(false);
function dfs(node, currentMin) {
visited[node] = true;
for (const [adj, dist] of graph[node]) {
if (!visited[adj]) {
currentMin = Math.min(currentMin, dist);
currentMin = dfs(adj, currentMin);
}
}
return currentMin;
}
return dfs(1, Infinity);
}#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
int graph[100001][101], edge[100001][101];
int g_size[100001];
bool visited[100001];
int minScoreDFS(int node, int minEdge, int n) {
visited[node] = true;
for (int i = 0; i < g_size[node]; i++) {
int adjacent = graph[node][i];
int dist = edge[node][i];
if (!visited[adjacent]) {
minEdge = minEdge < dist ? minEdge : dist;
minEdge = minScoreDFS(adjacent, minEdge, n);
}
}
return minEdge;
}
int minScore(int n, int** roads, int roadsSize, int* roadsColSize) {
for (int i = 1; i <= n; i++) {
visited[i] = false;
g_size[i] = 0;
}
for (int i = 0; i < roadsSize; i++) {
int a = roads[i][0];
int b = roads[i][1];
int d = roads[i][2];
graph[a][g_size[a]] = b;
edge[a][g_size[a]++] = d;
graph[b][g_size[b]] = a;
edge[b][g_size[b]++] = d;
}
return minScoreDFS(1, INT_MAX, n);
}using System;
using System.Collections.Generic;
public class Solution {
private int DFS(int node, bool[] visited, Dictionary<int, List<int[]>> graph, int currentMin) {
visited[node] = true;
foreach (var edge in graph[node]) {
int adj = edge[0];
int dist = edge[1];
if (!visited[adj]) {
currentMin = Math.Min(currentMin, dist);
currentMin = DFS(adj, visited, graph, currentMin);
}
}
return currentMin;
}
public int MinScore(int n, int[][] roads) {
var graph = new Dictionary<int, List<int[]>>();
for (int i = 1; i <= n; i++)
graph[i] = new List<int[]>();
foreach (var road in roads) {
graph[road[0]].Add(new int[]{road[1], road[2]});
graph[road[1]].Add(new int[]{road[0], road[2]});
}
var visited = new bool[n + 1];
return DFS(1, visited, graph, int.MaxValue);
}
}Python implementation captures the graph using a dictionary of lists. Using DFS starting from node 1, it identifies and updates the lowest edge score to connect to city n.
Time Complexity: O(V + E)
Space Complexity: O(V + E)
Approach 3: DFS
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.
function minScore(n: number, roads: number[][]): number {
const vis = new Array(n + 1).fill(false);
const g = Array.from({ length: n + 1 }, () => []);
for (const [a, b, v] of roads) {
g[a].push([b, v]);
g[b].push([a, v]);
}
let ans = Infinity;
const dfs = (i: number) => {
if (vis[i]) {
return;
}
vis[i] = true;
for (const [j, v] of g[i]) {
ans = Math.min(ans, v);
dfs(j);
}
};
dfs(1);
return ans;
}func minScore(n int, roads [][]int) int {
type pair struct{ i, v int }
g := make([][]pair, n)
for _, e := range roads {
a, b, d := e[0]-1, e[1]-1, e[2]
g[a] = append(g[a], pair{b, d})
g[b] = append(g[b], pair{a, d})
}
vis := make([]bool, n)
ans := 1 << 30
var dfs func(int)
dfs = func(i int) {
for _, nxt := range g[i] {
j, d := nxt.i, nxt.v
ans = min(ans, d)
if !vis[j] {
vis[j] = true
dfs(j)
}
}
}
dfs(0)
return ans
}impl Solution {
fn dfs(i: usize, mut ans: i32, g: &Vec<Vec<(usize, i32)>>, vis: &mut Vec<bool>) -> i32 {
if vis[i] {
return ans;
}
vis[i] = true;
for (j, v) in g[i].iter() {
ans = ans.min(*v.min(&Self::dfs(*j, ans, g, vis)));
}
ans
}
pub fn min_score(n: i32, roads: Vec<Vec<i32>>) -> i32 {
let n = n as usize;
let mut vis = vec![false; n + 1];
let mut g = vec![Vec::new(); n + 1];
for road in roads.iter() {
let a = road[0] as usize;
let b = road[1] as usize;
let v = road[2];
g[a].push((b, v));
g[b].push((a, v));
}
Self::dfs(1, i32::MAX, &g, &mut vis)
}
}Approach 4: BFS
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.
func minScore(n int, roads [][]int) int {
type pair struct{ i, v int }
g := make([][]pair, n)
for _, e := range roads {
a, b, d := e[0]-1, e[1]-1, e[2]
g[a] = append(g[a], pair{b, d})
g[b] = append(g[b], pair{a, d})
}
vis := make([]bool, n)
ans := 1 << 30
q := []int{0}
vis[0] = true
for len(q) > 0 {
for k := len(q); k > 0; k-- {
i := q[0]
q = q[1:]
for _, nxt := range g[i] {
j, d := nxt.i, nxt.v
ans = min(ans, d)
if !vis[j] {
vis[j] = true
q = append(q, j)
}
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Union-Find Data Structure | Time Complexity: O(E log* V) |
| BFS/DFS Traversal | Time Complexity: O(V + E) |
| DFS | – |
| BFS | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Score of a Path Between Two Cities easy or hard?
The problem is classified as Medium on LeetCode. The challenge is recognizing that the answer equals the smallest edge weight in the connected component containing city 1. Once that insight is clear, a simple BFS, DFS, or Union-Find implementation solves it efficiently.
Minimum Score of a Path Between Two Cities Python or Java solution?
Python and Java implementations typically use an adjacency list with BFS or DFS to traverse the graph. A variable tracks the smallest edge weight seen while visiting neighbors. The algorithm runs in O(n + m) time and requires O(n + m) space for the graph representation.
How to solve Minimum Score of a Path Between Two Cities in O(n + m)?
Construct an adjacency list and run BFS or DFS starting from city 1. While traversing neighbors, continuously update a variable storing the minimum road weight encountered. Since traversal covers the entire connected component of city 1, the smallest weight seen during exploration represents the minimum score of any valid path to city n.
What is the best approach for Minimum Score of a Path Between Two Cities?
The most practical approach is BFS or DFS traversal starting from city 1. Explore the entire connected component and track the smallest edge weight encountered. Since any path between city 1 and city n must stay inside this component, the minimum edge weight found during traversal becomes the answer. This runs in O(n + m) time.
Is Minimum Score of a Path Between Two Cities asked at Google/Amazon/Meta?
Graph connectivity and minimum edge problems are common in interviews at companies like Amazon, Google, and Meta. This problem specifically tests understanding of graph traversal and connected components using BFS, DFS, or Union-Find. Variations of this concept appear frequently in system design and algorithm interviews.
What data structure is used in Minimum Score of a Path Between Two Cities?
The problem primarily uses graph data structures such as adjacency lists for BFS or DFS traversal. Another common structure is Union-Find (Disjoint Set Union), which efficiently groups nodes into connected components and checks whether cities belong to the same set.
What is the time complexity of Minimum Score of a Path Between Two Cities?
The optimal solution runs in O(n + m) time where n is the number of cities and m is the number of roads. BFS or DFS visits each node and edge once while tracking the minimum weight. The Union-Find solution runs in O(m α(n)) due to nearly constant-time union and find operations.