Reverse Graph | BFS | Binary search | Easy to understand
IntuitionThe goal is to minimize the maximum edge weight in a directed graph while ensuring:
All nodes can reach node 0.
Each node has at most threshold outgoin
# Intuition
The goal is to minimize the maximum edge weight in a directed graph while ensuring:
1. All nodes can reach node `0`.
2. Each node has at most `threshold` outgoing edges.

This problem can be tackled by treating the edge weights as a binary search problem. We iteratively check if the graph can satisfy the conditions for a given maximum edge weight.

# Approach
1. **Binary Search for Edge Weight**:
   - Identify the range of edge weights, from the minimum weight in `edges` to the maximum.
   - Perform binary search over this range to find the smallest possible maximum weight for which the conditions are satisfied.

2. **Validation using BFS**:
   - For a given maximum weight (`mid`), construct a reversed adjacency list of edges with weight ≤ `mid`.
   - Use BFS to check if all nodes can reach node `0` in this reduced graph.

3. **Handling Edge Removal**:
   - During graph construction, ignore edges with weight > `mid` and validate only those that satisfy the threshold condition.

4. **Result**:
   - If the conditions are satisfied for a given `mid`, move the search range towards smaller weights.
   - If not, adjust the range towards larger weights.

# Complexity
- **Time Complexity**:
  - Let `m` be the number of edges and `n` be the number of nodes.
  - Binary search runs in `O(log(maxW - minW))`.
  - Each validation (BFS) step involves traversing all edges once, i.e., `O(m)`.
  - Total: `O(mlog(maxW - minW))`.

- **Space Complexity**:
  - Storing the adjacency list requires `O(m)`.
  - BFS uses `O(n)` for the visited array and queue.
  - Total: `O(m + n)`.


# Code
```java []
class Solution {
    public int minMaxWeight(int n, int[][] edges, int threshold) {
        int minW = Integer.MAX_VALUE;
        int maxW = Integer.MIN_VALUE;
        for (int[] edge : edges) {
            minW = Math.min(minW, edge[2]);
            maxW = Math.max(maxW, edge[2]);
        }

        int l = minW;
        int r = maxW;
        int ans = -1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (possible(n, edges, mid)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;

    }

    private boolean possible(int n, int[][] edges, int max) {
        HashMap<Integer, List<Integer>> adj = new HashMap<>();

        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            int wt = edge[2];

            if (wt <= max) {
                if (!adj.containsKey(to)) {
                    adj.put(to, new ArrayList<>());
                }
                adj.get(to).add(from);
            }
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        int count = 0;

        while (!q.isEmpty()) {
            int curr = q.remove();
            if (visited[curr]) {
                continue;
            }
            visited[curr] = true;
            count++;
            if (adj.get(curr) != null)
                for (int next : adj.get(curr)) {
                    q.add(next);
                }

        }
        return count == n;

    }

}
```
['Binary Search', 'Breadth-First Search', 'Graph', 'Java']