Minimize the maximum edge weight of graph

Binary Search Depth-First Search Breadth-First Search Graph Theory Shortest Path

44.0% acceptance

Feb 25, 2026

242

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn min_max_weight(n: i32, edges: Vec<Vec<i32>>, _threshold: i32) -> i32 {
    let n = n as usize;
    // Build reverse graph adjacency list
    let mut rev_adj: Vec<Vec<(usize, i32)>> = vec![vec![]; n];
    let mut all_weights: Vec<i32> = Vec::new();
    for e in &edges {
      let a = e[0] as usize;
      let b = e[1] as usize;
      let w = e[2];
      rev_adj[b].push((a, w));
      all_weights.push(w);
    }
    all_weights.sort();
    all_weights.dedup();
    // Check connectivity with edges <= w_max using BFS
    let check = |w_max: i32| -> bool {
      let mut visited = vec![false; n];
      visited[0] = true;
      let mut queue = std::collections::VecDeque::new();
      queue.push_back(0usize);
      let mut count = 1usize;
      while let Some(u) = queue.pop_front() {
        for &(v, w) in &rev_adj[u] {
          if !visited[v] && w <= w_max {
            visited[v] = true;
            count += 1;
            queue.push_back(v);
          }
        }
      }
      count == n
    };
    if all_weights.is_empty() { return if n == 1 { 0 } else { -1 }; }
    if !check(*all_weights.last().unwrap()) { return -1; }
    let mut lo = 0usize;
    let mut hi = all_weights.len() - 1;
    while lo < hi {
      let mid = (lo + hi) / 2;
      if check(all_weights[mid]) { hi = mid; } else { lo = mid + 1; }
    }
    all_weights[lo]
  }
}