Katkat
Back

Minimize the Maximum Edge on a Path

Walmart LabsSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Find a path in a weighted undirected graph that minimizes its largest edge rather than the sum of weights. Handle parallel edges, disconnected vertices, and the start-equals-target case efficiently at large graph scale.

Minimize the Maximum Edge on a Path

You are given a weighted undirected graph and two vertices, start and target. Define the stress of a path as the largest edge weight used by that path. Return the minimum possible stress among all paths from start to target. Return -1 when no such path exists.

Function Signature

def minimum_path_stress(
 n: int,
 edges: list[tuple[int, int, int]],
 start: int,
 target: int,
) -> int:
 ...

Input

  • Vertices are numbered from 0 through n - 1.
  • Each edge is (u, v, weight) and may be traversed in either direction.
  • Parallel edges are allowed.

Output

Return the smallest achievable maximum edge weight, or -1 if target is unreachable. If start == target, return 0.

Constraints

  • 1 <= n <= 200_000
  • 0 <= len(edges) <= 300_000
  • 1 <= weight <= 10**9
  • 0 <= start, target < n

Example

n = 5
edges = [(0, 1, 8), (0, 2, 3), (2, 1, 4), (1, 3, 6), (2, 3, 10)]
start = 0
target = 3

Output: 6

The path 0 -> 2 -> 1 -> 3 has edge weights 3, 4, 6, so its stress is 6. No path reaches vertex 3 using only edges lighter than 6.

Clarifications

  • Minimize the largest edge, not the sum of edge weights.
  • The graph is not guaranteed to be connected.