Katkat
Back

Find the Minimum Edge Score on a Path Between Two Cities

VisaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests the ability to optimize for the bottleneck edge in a path rather than the total path cost, typically solvable using a modified Dijkstra's algorithm or a Union-Find approach.

Problem Statement

You are given n cities labeled 0 to n-1 and a list of bidirectional roads. Each road connects two cities and has an associated weight representing the road's congestion score.

The "path score" of any given route is defined as the maximum congestion score of any individual edge on that route. Your goal is to find a path between city start and city end such that the path score is minimized. If no path exists, return -1.

Function Signature

def min_path_score(n: int, roads: List[List[int]], start: int, end: int) -> int:

Constraints

  • 2 <= n <= 10^5
  • `1 1->2 has edges {10, 5}, max is 10. Path 0->2 has edge {20}, max is 20. Minimized max is 10.

Example 2:

  • roads = [[0, 1, 5], [2, 3, 2]], start = 0, end = 3
  • Output: -1
  • Explanation: The graph is disconnected; no path exists.

Edge Cases

  • Start and end cities are the same (score 0).
  • The graph is disconnected.
  • Multiple roads between the same two cities with different weights.

Hints

Hint 1

Instead of minimizing the sum of weights, consider how the bottleneck changes as you add edges to the graph.

Hint 2

If you sort all edges by weight in ascending order and add them one by one to a Union-Find structure, you can determine connectivity efficiently.

Hint 3

Alternatively, modify Dijkstra's algorithm to update the minimum bottleneck score to reach each node rather than the cumulative sum.

Follow-up questions

  • How would you modify your solution if you were restricted to a path with a maximum number of edges `k`?
  • Explain how the time complexity would change if you used a Binary Search on the possible edge weights combined with a BFS check.
  • If the graph were directed rather than undirected, would your Union-Find approach still be applicable? Why or why not?