FastPrep
Problem · Graph

Minimum Stress Path

Learn this problem
● MediumWalmartOA

Problem statement

You are given a weighted undirected graph with graph_nodes nodes numbered from 1 through graph_nodes. The arrays graph_from, graph_to, and graph_weight describe the graph's edges: edge i connects graph_from[i] and graph_to[i] with weight graph_weight[i].

The stress level of a path is the maximum edge weight on that path.

Return the minimum possible stress level among all paths from source to destination. If no such path exists, return -1. If source = destination, return 0.

Although the endpoint arrays are named graph_from and graph_to, every edge is undirected.

Function

getMinimumStress(graph_nodes: int, graph_from: int[], graph_to: int[], graph_weight: int[], source: int, destination: int) → int

Examples

Example 1

graph_nodes = 4graph_from = [2,2,1,4]graph_to = [1,3,4,3]graph_weight = [100,200,10,20]source = 1destination = 3return = 20

The weighted undirected graph has two branches from node 1 to node 3:

Weighted undirected graph
​​​
​(3)​
200 ↗​↖ 20
(2)​(4)
↖ 100​10 ↗
​(1)​
  1. The path 1 -> 2 -> 3 has stress max(100, 200) = 200.
  2. The path 1 -> 4 -> 3 has stress max(10, 20) = 20.

The minimum possible stress is 20.

Constraints

  • 1 <= graph_nodes <= 10^5.
  • 1 <= graph_from.length = graph_to.length = graph_weight.length <= 10^5.
  • 1 <= graph_from[i], graph_to[i], source, destination <= graph_nodes.
  • 0 <= graph_weight[i] <= 10^9.

More Walmart problems

drafts saved locally
public int getMinimumStress(int graph_nodes, int[] graph_from, int[] graph_to, int[] graph_weight, int source, int destination) {
  // write your code here
}
graph_nodes4
graph_from[2,2,1,4]
graph_to[1,3,4,3]
graph_weight[100,200,10,20]
source1
destination3
expected20
checking account