Practice/Amazon/Leetcode 2492. Minimum Score of a Path Between Two Cities

Leetcode 2492. Minimum Score of a Path Between Two Cities

CodingOptional

Problem

You are managing a transportation network with n cities numbered from 1 to n. The cities are connected by bidirectional roads, where each road has a quality score representing its reliability.

Given the total number of cities n and a list of roads where roads[i] = [cityA, cityB, quality] represents a bidirectional road between cityA and cityB with quality score quality, find the minimum quality score among all roads that are part of any valid route from city 1 to city n.

A route's accessibility is determined by its weakest link—the road with the lowest quality score. You need to find what the lowest quality road score would be considering all possible paths that keep cities 1 and n connected in the network.

Note that you don't need to find a specific path; you only need to determine the minimum road quality score that exists within the connected network containing both city 1 and city n.

Requirements

1. Return the minimum quality score among all roads in the connected component containing cities 1 and n
2. The roads are bidirectional (can be traversed in both directions)
3. It is guaranteed that cities 1 and n are connected through the network

Constraints

• 2 ≤ n ≤ 105
• 1 ≤ roads.length ≤ 105
• roads[i].length == 3
• 1 ≤ cityA, cityB ≤ n
• cityA ≠ cityB
• 1 ≤ quality ≤ 104
• There are no duplicate roads
• There exists at least one path from city 1 to city n

Examples

Example 1:

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]] Output: 5 Explanation: The network forms a connected component with all 4 cities. The road from city 2 to city 4 has quality 5, which is the minimum among all roads in this component (5, 6, 7, 9).

Example 2:

Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]] Output: 2 Explanation: All cities are connected in one component. The road between cities 1 and 2 has the minimum quality of 2.

Example 3:

Input: n = 2, roads = [[1,2,10]] Output: 10 Explanation: Only one road exists, so its quality score is both the maximum and minimum.