Minimum Score of a Path Between Two Cities

Medium
932.

Minimum Score of a Path Between Two Cities

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.

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^5
  • 1 <= roads.length <= 10^5
  • roads[i].length == 3
  • 1 <= a, b <= n
  • a != b
  • 1 <= distance <= 10^4
  • There are no repeated edges.
  • City n is reachable from city 1.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var minScore = function(n, roads) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= roads.length <= 10^5
  • roads[i].length == 3
  • 1 <= a, b <= n
  • a != b
  • 1 <= distance <= 10^4
  • There are no repeated edges.
  • City n is reachable from city 1.

Hints for Minimum Score of a Path Between Two Cities

  1. Hint 1

    A path may wander freely and reuse roads, so it can take in any road in the connected component it starts from.

  2. Hint 2

    So the shape of the path is irrelevant — only which roads are reachable.

  3. 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

  1. Union the endpoints of every road.
  2. Find the component root of city 1 — city n is in it by assumption.
  3. 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)