Minimum Score of a Path Between Two Cities

Minimum Score of a Path Between Two Cities

What is this problem about?

The Minimum Score of a Path Between Two Cities problem presents a graph of n cities connected by roads, each with a distance score. You need to find the minimum distance road on any path connecting city 1 to city n. Crucially, the path does not need to be simple — you can revisit nodes and edges. This Minimum Score of a Path Between Two Cities coding problem is really asking about the minimum edge weight in the connected component containing both node 1 and node n.

Why is this asked in interviews?

Amazon, Google, and Unbxd ask this to test graph connectivity reasoning. Candidates who miss the key insight — that you can revisit edges, so the path is just the connected component — often waste time building shortest-path algorithms. The union find, BFS, DFS, and graph interview pattern is central, and the problem rewards candidates who simplify the problem statement before reaching for complex algorithms.

Algorithmic pattern used

The pattern is Union-Find (or BFS/DFS) to find connected components. Find all nodes reachable from node 1 (or equivalently, in the same component as node 1 and node n). Among all edges connecting nodes in this component, return the minimum edge weight. Since paths can revisit nodes, the "minimum score path" is simply the minimum edge in the entire connected component.

Example explanation

Graph: nodes 1-2-3-4-5. Edges: (1,2,5), (2,3,3), (3,4,7), (4,5,2), (1,5,9). All 5 nodes are in one connected component (node 1 reaches node 5). All edge weights: 5, 3, 7, 2, 9. Minimum = 2 (edge between 4 and 5).

Common mistakes candidates make

• Running Dijkstra or BFS/DFS looking for the min-edge path (not necessary since revisiting is allowed).
• Only considering edges on the shortest path instead of all edges in the component.
• Not verifying that node 1 and node n are actually connected (could be a disconnected graph).
• Using a complex algorithm when a simple BFS + min scan suffices.

Interview preparation tip

Always read problem constraints for graph problems, especially whether paths can revisit nodes. "Revisiting allowed" transforms a shortest-path problem into a connectivity problem — a massive simplification. Practice recognizing this pattern, as it appears in several medium graph problems. Union-Find is particularly elegant here: find the component containing 1 and n, then scan all edges within it for the minimum weight.