✅BFS + Binary Search (Very intuitive) | JAVA | Easy Explanation 💎
Hi , Everyone this was intresting question (Out of the box) in weekly
I hope you understand the explanation!Points to think on :
given constraints :
1 <= thresh
Hi , Everyone this was intresting question (Out of the box) in weekly 
I hope you understand the explanation!
# Points to think on : 
- given constraints : 
1 <= threshold <=n-1 
this means that we can remove all the edges from the node 
and can keep the only one edge that connects that node to the node 0 
right!! 
- Rather than DFS from all the nodes to reach to the node 0 we can simply do a BFS from the node 0 and try to reach all the nodes, For this we will be needing to reverse the graph 
- We will go super Greedy and try to check whether the least weight edge will satisfy our conditions 
- If not then we will increase the weight and again check with it 


SO The intuition is that 
- We will be storing the min and max weight from the edges given 
- Try binary search to get the least weighted edge that will satisfy the conditions 
- return the less weighted edge 
```
    int l = minW ; 
    int r = maxW ; 
    while(l <= r){
        int mid = l + (r-l)/2 ;
        if(isPossible(n , edges , mid)){
            ans = mid ;
            r = mid-1 ; 
        }else{
            l = mid+1 ;
        }
    }
```
Now comes how do we check whether the chosen weight satisfies the condtions 
```
public boolean isPossible(int n, int[][] edges, int threshold)
```
so we will set a bar 'threshold' 
above this all the edges are not counted in the graph or say not included in the graph 
the graph we are making will be a reverse graph 
```
 List<List<Integer>> revGraph = new ArrayList<>();
    for(int i = 0 ; i < n ; i++) revGraph.add(new ArrayList<>());
    for(int[] edge : edges){
        int u = edge[0];
        int v = edge[1];
        if(edge[2] <= threshold){
            revGraph.get(v).add(u);
        }
    }
```
Implementing BFS from node '0' and checking whther it is possible to reach to all the nodes by checking the count 
```
    boolean[] visited = new boolean[n];
    Queue<Integer> q = new LinkedList<>();
    q.offer(0);
    visited[0] = true ;
    int count = 1 ;

    while(!q.isEmpty()){
        int curr = q.poll();
        for(Integer neighbor : revGraph.get(curr)){
            if(visited[neighbor] == false){
                visited[neighbor] = true ; 
                q.add(neighbor);
                count++ ;
            }
        }
    }
```
if it comes out to be true that is we are able to reach to all the nodes 
then we will try to minimize the weight for more greedy solution 
thus using binary search for that 

Upvote if the explanation was helpful 
Thanks!


# Code
```java []
class Solution {
    public int minMaxWeight(int n, int[][] edges, int threshold) {
        int minW = Integer.MAX_VALUE ;
        int maxW = 0 ; 
        for(int[] edge : edges){
            minW = Math.min(minW , edge[2]);
            maxW = Math.max(maxW , edge[2]);
        }
        int ans = -1 ; 
        int l = minW ; 
        int r = maxW ; 
        while(l <= r){
            int mid = l + (r-l)/2 ;
            if(isPossible(n , edges , mid)){
                ans = mid ;
                r = mid-1 ; 
            }else{
                l = mid+1 ;
            }
        }
        return ans ; 
    }
    public boolean isPossible(int n, int[][] edges, int threshold) {
        List<List<Integer>> revGraph = new ArrayList<>();
        for(int i = 0 ; i < n ; i++) revGraph.add(new ArrayList<>());
        for(int[] edge : edges){
            int u = edge[0];
            int v = edge[1];
            if(edge[2] <= threshold){
                revGraph.get(v).add(u);
            }
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
        visited[0] = true ;
        int count = 1 ;

        while(!q.isEmpty()){
            int curr = q.poll();
            for(Integer neighbor : revGraph.get(curr)){
                if(visited[neighbor] == false){
                    visited[neighbor] = true ; 
                    q.add(neighbor);
                    count++ ;
                }
            }
        }
        return count == n ;
    }

}
```
['Java']