Skip to main content
Talentd

Minimize the Maximum Edge Weight of Graph - Solution & Explanation

MediumBinary SearchDepth-First SearchBreadth-First SearchGraph4 min readAsked at: Uber, Google
Practice this problem

Problem Statement

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:

  • Node 0 must be reachable from all other nodes.
  • The maximum edge weight in the resulting graph is minimized.
  • Each node has at most 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 <= 105
  • 1 <= threshold <= n - 1
  • 1 <= edges.length <= min(105, n * (n - 1) / 2).
  • edges[i].length == 3
  • 0 <= Ai, Bi < n
  • Ai != Bi
  • 1 <= Wi <= 106
  • There may be multiple edges between a pair of nodes, but they must have unique weights.

Approach Overview

Problem 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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/DFSO(E log W)O(V)When edge weights have a clear numeric range and feasibility checking is simple
Minimum Spanning Tree PathO(E log V)O(V)When MST is already computed or when analyzing minimax path properties

Video Solution

Minimize the Maximum Edge Weight of Graph | Detailed Intuition | BFS | DFS | Leetcode 3419 | MIK • codestorywithMIK • 4,992 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimize the Maximum Edge Weight of Graph easy or hard?
This problem is generally classified as Medium difficulty. The challenge comes from recognizing that the objective is not minimizing total distance but minimizing the maximum edge weight. Once you identify the minimax property, the solution follows using either modified Dijkstra or binary search with BFS/DFS.
Minimize the Maximum Edge Weight of Graph Python/Java solution
The solution typically uses adjacency lists and either a priority queue (for the Dijkstra minimax approach) or BFS/DFS inside a binary search loop. Python implementations use heapq for the priority queue, while Java commonly uses PriorityQueue and ArrayList for graph representation.
How to solve Minimize the Maximum Edge Weight of Graph in O(E log V)?
Use a modified Dijkstra algorithm that tracks the minimum possible maximum edge weight to reach each node. Instead of summing edge weights, propagate the value max(currentCost, edgeWeight). A priority queue always processes the node with the smallest current maximum edge value, ensuring the optimal minimax path is found efficiently.
What is the best approach for Minimize the Maximum Edge Weight of Graph?
The most common approach is binary search on the edge weight combined with BFS or DFS for reachability. For a candidate maximum weight X, ignore edges heavier than X and check if the destination is reachable. This runs in O(E log W) time where W is the weight range. A modified Dijkstra that minimizes the maximum edge on the path is also a strong optimal solution with O(E log V) complexity.
Is Minimize the Maximum Edge Weight of Graph asked at Google/Amazon/Meta?
Minimax path and threshold graph problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often involve minimizing the maximum edge, limiting path constraints, or combining binary search with graph traversal. Understanding both Dijkstra variants and binary search on answers is valuable for these interviews.
What data structure is used in Minimize the Maximum Edge Weight of Graph?
Key data structures include adjacency lists for graph representation and a priority queue for the modified Dijkstra solution. The binary search approach uses BFS or DFS with a queue or recursion stack along with a visited set or boolean array.
What is the time complexity of Minimize the Maximum Edge Weight of Graph?
Using a modified Dijkstra algorithm, the time complexity is O(E log V) due to priority queue operations. The binary search plus BFS/DFS approach runs in O(E log W), where W represents the possible range of edge weights. Both solutions use O(V) auxiliary space for visited or distance tracking.

Ready to solve this problem?

Practice Minimize the Maximum Edge Weight of Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Median of Two Sorted Arrays

Next

Search in Rotated Sorted Array