Watch 7 video solutions for Minimize the Maximum Edge Weight of Graph, a medium level problem involving Binary Search, Depth-First Search, Breadth-First Search. This walkthrough by codestorywithMIK has 4,506 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integers, n and threshold, as well as a directed weighted graph of n nodes numbered from 0 to n - 1. The graph is represented by a 2D integer array edges, where edges[i] = [Ai, Bi, Wi] indicates that there is an edge going from node Ai to node Bi with weight Wi.
You have to remove some edges from this graph (possibly none), so that it satisfies the following conditions:
threshold outgoing edges.Return the minimum possible value of the maximum edge weight after removing the necessary edges. If it is impossible for all conditions to be satisfied, return -1.
Example 1:
Input: n = 5, edges = [[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]], threshold = 2
Output: 1
Explanation:
Remove the edge 2 -> 0. The maximum weight among the remaining edges is 1.
Example 2:
Input: n = 5, edges = [[0,1,1],[0,2,2],[0,3,1],[0,4,1],[1,2,1],[1,4,1]], threshold = 1
Output: -1
Explanation:
It is impossible to reach node 0 from node 2.
Example 3:
Input: n = 5, edges = [[1,2,1],[1,3,3],[1,4,5],[2,3,2],[3,4,2],[4,0,1]], threshold = 1
Output: 2
Explanation:
Remove the edges 1 -> 3 and 1 -> 4. The maximum weight among the remaining edges is 2.
Example 4:
Input: n = 5, edges = [[1,2,1],[1,3,3],[1,4,5],[2,3,2],[4,0,1]], threshold = 1
Output: -1
Constraints:
2 <= n <= 1051 <= threshold <= n - 11 <= edges.length <= min(105, n * (n - 1) / 2).edges[i].length == 30 <= Ai, Bi < nAi != Bi1 <= Wi <= 106Problem Overview: You are given a weighted graph and need a path where the largest edge weight used is as small as possible. Instead of minimizing the sum of weights, the goal is to minimize the maximum edge weight along the chosen path.
Approach 1: Modified Dijkstra (Minimax Path) (Time: O(E log V), Space: O(V))
This problem can be treated as a variation of shortest path. Instead of tracking the total distance, store the smallest possible maxEdge needed to reach each node. When exploring an edge (u → v) with weight w, update the state as newCost = max(currentCost, w). Use a priority queue that always expands the node with the smallest current maximum edge weight. This works because once a node is processed with the minimal possible maximum weight, any later path will only increase that value.
Approach 2: Binary Search + Graph Traversal (Time: O(E log W), Space: O(V))
Another perspective: if you fix a maximum allowed edge weight X, the problem reduces to checking if a path exists using only edges ≤ X. The feasibility check can be done with Breadth-First Search or Depth-First Search. Binary search over the answer range (from the smallest to largest edge weight). For each midpoint, run BFS/DFS ignoring edges heavier than the threshold. If the destination becomes reachable, the threshold is feasible and you try a smaller value.
Approach 3: Minimum Spanning Tree Observation (Time: O(E log V), Space: O(V))
The minimax property of paths in an MST provides another insight. In a Minimum Spanning Tree, the maximum edge weight on the path between two nodes is minimized among all possible paths in the original graph. Construct the MST using Kruskal or Prim, then find the path between the required nodes and return the largest edge weight along that path.
Recommended for interviews: Binary search with BFS/DFS is often the most intuitive explanation because it directly models the decision question: “Can a path exist if the maximum edge weight is ≤ X?”. The modified Dijkstra solution is equally strong and often considered the cleanest implementation for production code. Mentioning both shows strong understanding of graph algorithms and optimization techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modified Dijkstra (Minimax Path) | O(E log V) | O(V) | General case when you want the optimal minimax path directly |
| Binary Search + BFS/DFS | O(E log W) | O(V) | When edge weights have a clear numeric range and feasibility checking is simple |
| Minimum Spanning Tree Path | O(E log V) | O(V) | When MST is already computed or when analyzing minimax path properties |