# Minimize the Maximum Edge Weight of Graph
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimize-the-maximum-edge-weight-of-graph)
Canonical: https://scaleengineer.com/dsa/problems/minimize-the-maximum-edge-weight-of-graph
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimize-the-maximum-edge-weight-of-graph/image0.png)

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:** 

![](https://assets.glich.co/dsa/minimize-the-maximum-edge-weight-of-graph/image1.png)

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.

# Approaches
## Approach 1: Linear Scan on Maximum Weight
A straightforward but less efficient approach is to iterate through all possible values for the answer. The answer must be one of the weights present in the `edges` array. We can test each unique edge weight, one by one, in increasing order, as a candidate for the maximum allowed weight. The first weight for which we can satisfy all conditions will be our minimized maximum weight.
**Time:** O(k * (V + E)), where k is the number of unique edge weights. In the worst case, k can be equal to E, leading to a complexity of O(E * (V + E)), which is too slow for the given constraints. · **Space:** O(V + E), where V is the number of nodes (n) and E is the number of edges. This is for storing the adjacency list and the visited array/queue for BFS.
**Pros:** Conceptually simple and easy to implement.; Correctly solves the problem.
**Cons:** The time complexity is too high for the given constraints, as it may require checking a large number of unique weights.
### Explanation
For a given candidate maximum weight `max_w`, we need a way to check if a valid subgraph exists. A subgraph is valid if:
1. All its edges have weights `<= max_w`.
2. All other nodes can reach node 0.
3. Every node's out-degree is at most `threshold`.

The crucial insight is that if reachability is possible (condition 2), we can always satisfy the out-degree constraint (condition 3). This is because if every node can reach node 0, we can form a spanning arborescence rooted at 0 on the graph of reachable nodes. In such an arborescence, every node except the root has an out-degree of exactly 1. Since the problem states `threshold >= 1`, this out-degree of 1 will always be less than or equal to `threshold`. Therefore, the check for a given `max_w` simplifies to just verifying reachability.

To check reachability, we can build a graph containing only edges with weight `<= max_w`, reverse all the edges, and then run a single BFS/DFS from node 0 to see if all nodes in the graph are visited. If they are, a valid subgraph exists.

This approach iterates through each unique weight and performs a full graph traversal, which can be slow if there are many unique weights.

```java
import java.util.*;

class Solution {
    public int minimizeMaxWeight(int n, int[][] edges, int threshold) {
        Set<Integer> weightSet = new HashSet<>();
        for (int[] edge : edges) {
            weightSet.add(edge[2]);
        }
        List<Integer> sortedWeights = new ArrayList<>(weightSet);
        Collections.sort(sortedWeights);

        for (int maxWeight : sortedWeights) {
            if (check(n, edges, maxWeight)) {
                return maxWeight;
            }
        }

        return -1;
    }

    private boolean check(int n, int[][] edges, int maxWeight) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            if (edge[2] <= maxWeight) {
                // Reversed edge: v -> u for original u -> v
                adj.get(edge[1]).add(edge[0]);
            }
        }

        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n];
        int count = 0;

        q.offer(0);
        visited[0] = true;
        count++;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.offer(v);
                    count++;
                }
            }
        }

        return count == n;
    }
}
```
### Algorithm
1. **Identify Search Space**: The possible values for the maximum edge weight range from the minimum weight present in the graph to the maximum. We can collect all unique weights and sort them to define an ordered search space.
2. **Linear Scan**: Iterate through each unique weight `w` from the sorted list, from smallest to largest.
3. **Check Feasibility**: For each `w`, treat it as the potential maximum allowed weight (`max_w`). We need to check if it's possible to satisfy the problem's conditions with this `max_w`.
4. **Feasibility Check (`check(max_w)`)**: 
    a. Construct a temporary graph containing only the edges from the input with weight less than or equal to `max_w`.
    b. The condition that node 0 must be reachable from all other nodes is equivalent to checking if all other nodes are reachable from node 0 in the *reversed* graph.
    c. Build the reversed graph.
    d. Perform a graph traversal (like Breadth-First Search or Depth-First Search) starting from node 0 on the reversed graph.
    e. If the traversal visits all `n` nodes, it means a valid subgraph can be formed, and the function returns `true`.
5. **Find First Valid Weight**: The first `w` for which `check(w)` returns `true` is the minimum possible maximum weight. Return this `w`.
6. **Handle Impossible Case**: If the loop completes and no such `w` is found, it's impossible to satisfy the conditions. Return -1.

## Approach 2: Binary Search on the Answer
This problem has a monotonic property: if we can find a valid subgraph with a maximum edge weight of `W`, we can certainly also find one for any maximum weight `W' > W` (since the set of allowed edges only grows). This property allows us to use binary search on the answer (the maximum allowed weight). We can efficiently search for the smallest possible value of `max_w` for which a valid subgraph exists.
**Time:** O((V + E) * log(W_max)), where V is the number of nodes, E is the number of edges, and W_max is the maximum possible edge weight. The `log(W_max)` factor comes from the binary search, and the `(V + E)` factor is the cost of the `check` function (building the graph and running BFS). · **Space:** O(V + E), where V is the number of nodes (n) and E is the number of edges. This space is used for the adjacency list representation of the graph and the data structures for BFS (queue and visited array).
**Pros:** Highly efficient and passes within the time limits.; Effectively reduces the search space for the answer.
**Cons:** Slightly more complex to reason about than a simple linear scan.
### Explanation
The core of this approach is the binary search framework combined with the same `check(max_w)` function from the previous approach. The binary search dramatically reduces the number of times we need to call the `check` function.

Instead of checking every unique weight, we check the middle value `mid` of our current search range `[low, high]`. 
- If `check(mid)` is true, we know that a solution exists for `max_w = mid`. This means `mid` is a potential answer, and there might be an even better (smaller) one. So, we record `mid` as our current best answer and narrow our search to the lower half: `high = mid - 1`.
- If `check(mid)` is false, it's impossible to satisfy the conditions with the current `max_w`. We must allow edges with higher weights, so we narrow our search to the upper half: `low = mid + 1`.

This process continues until `low > high`, at which point we have found the minimum `max_w` that works.

The logic for the `check(max_w)` function remains the same: it verifies that if we only consider edges with weight at most `max_w`, it's possible for all nodes to reach node 0. As explained before, the `threshold` constraint is implicitly satisfied if reachability is met, because we can always construct a subgraph (a spanning arborescence) where each node's out-degree is at most 1.

```java
import java.util.*;

class Solution {
    public int minimizeMaxWeight(int n, int[][] edges, int threshold) {
        int low = 0, high = 1000001; // Weights are 1 to 10^6. Range [0, 10^6+1] is safe.
        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (check(n, edges, mid)) {
                ans = mid;
                high = mid - 1; // Try for an even smaller max weight
            } else {
                low = mid + 1; // Need to allow larger weights
            }
        }
        return ans;
    }

    private boolean check(int n, int[][] edges, int maxWeight) {
        // Build the reversed graph with edges having weight <= maxWeight
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            if (edge[2] <= maxWeight) {
                // Add reversed edge: v -> u for original u -> v
                adj.get(edge[1]).add(edge[0]);
            }
        }

        // Run BFS from node 0 on the reversed graph to check reachability
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[n];
        int count = 0;

        q.offer(0);
        visited[0] = true;
        count++;

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.offer(v);
                    count++;
                }
            }
        }

        // If all n nodes are visited, a valid subgraph exists
        return count == n;
    }
}
```
### Algorithm
1. **Binary Search on the Answer**: The problem asks to minimize a maximum value, which suggests binary search on the answer. The range of possible answers is from 1 to the maximum possible weight (10^6).
2. **Define Search Range**: Initialize `low = 0`, `high = 10^6 + 1`, and `ans = -1`.
3. **Binary Search Loop**: While `low <= high`:
    a. Calculate `mid = low + (high - low) / 2` as the candidate for the maximum allowed weight.
    b. Call a helper function `check(mid)` to determine if it's possible to satisfy the conditions with `mid` as the maximum weight.
    c. If `check(mid)` returns `true`, it means `mid` is a possible answer. We store it and try for an even smaller maximum weight by setting `high = mid - 1`.
    d. If `check(mid)` returns `false`, `mid` is too small. We need to allow larger weights, so we set `low = mid + 1`.
4. **Return Result**: After the loop, `ans` will hold the minimum maximum weight found, or -1 if no solution is possible.
5. **`check(max_w)` function**: This function is identical to the one in the Linear Scan approach. It builds a reversed graph with edges of weight `<= max_w` and runs a traversal from node 0 to check if all `n` nodes are reachable.