3419. Minimize the Maximum Edge Weight of Graph LeetCode Solution

In this guide, you will get 3419. Minimize the Maximum Edge Weight of Graph LeetCode Solution with the best time and space complexity. The solution to Minimize the Maximum Edge Weight of Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimize the Maximum Edge Weight of Graph solution in C++
Minimize the Maximum Edge Weight of Graph solution in Java
Minimize the Maximum Edge Weight of Graph solution in Python
Additional Resources

3419. Minimize the Maximum Edge Weight of Graph LeetCode Solution image

Problem Statement of Minimize the Maximum Edge Weight of Graph

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

3419. Minimize the Maximum Edge Weight of Graph LeetCode Solution in C++

class Solution {
 public:
  int minMaxWeight(int n, vector<vector<int>>& edges, int threshold) {
    constexpr int kMax = 1'000'000;
    vector<vector<pair<int, int>>> reversedGraph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      reversedGraph[v].push_back({u, w});
    }

    int l = 1;
    int r = kMax + 1;

    while (l < r) {
      const int m = (l + r) / 2;
      if (dfs(reversedGraph, 0, m, vector<bool>(n)) == n)
        r = m;
      else
        l = m + 1;
    }

    return l == (kMax + 1) ? -1 : l;
  }

 private:
  // Returns the number of nodes reachable from u with weight <= m.
  int dfs(const vector<vector<pair<int, int>>>& reversedGraph, int u,
          int maxWeight, vector<bool>&& seen) {
    int res = 1;
    seen[u] = true;
    for (const auto& [v, w] : reversedGraph[u]) {
      if (w > maxWeight || seen[v])
        continue;
      res += dfs(reversedGraph, v, maxWeight, std::move(seen));
    }
    return res;
  }
};
/* code provided by PROGIEZ */

3419. Minimize the Maximum Edge Weight of Graph LeetCode Solution in Java

class Solution {
  public int minMaxWeight(int n, int[][] pairs, int threshold) {
    final int kMax = 1_000_000;
    List<Pair<Integer, Integer>>[] reversedGraph = new List[n];

    for (int i = 0; i < n; i++)
      reversedGraph[i] = new ArrayList<>();

    for (int[] pair : pairs) {
      final int u = pair[0];
      final int v = pair[1];
      final int w = pair[2];
      reversedGraph[v].add(new Pair<>(u, w));
    }

    int l = 1;
    int r = kMax + 1;

    while (l < r) {
      final int m = (l + r) / 2;
      if (dfs(reversedGraph, 0, m, new boolean[n]) == n)
        r = m;
      else
        l = m + 1;
    }

    return l == (kMax + 1) ? -1 : l;
  }

  // Returns the number of nodes reachable from u with weight <= maxWeight.
  private int dfs(List<Pair<Integer, Integer>>[] reversedGraph, int u, int maxWeight,
                  boolean[] seen) {
    int res = 1;
    seen[u] = true;
    for (Pair<Integer, Integer> pair : reversedGraph[u]) {
      final int v = pair.getKey();
      final int w = pair.getValue();
      if (w > maxWeight || seen[v])
        continue;
      res += dfs(reversedGraph, v, maxWeight, seen);
    }
    return res;
  }
}
// code provided by PROGIEZ

3419. Minimize the Maximum Edge Weight of Graph LeetCode Solution in Python

class Solution:
  def minMaxWeight(self, n: int, edges: list[list[int]], threshold: int) -> int:
    kMax = 1000000
    reversedGraph = [[] for _ in range(n)]

    for u, v, w in edges:
      reversedGraph[v].append((u, w))

    l = 1
    r = kMax + 1

    while l < r:
      m = (l + r) // 2
      if self._dfs(reversedGraph, 0, m, set()) == n:
        r = m
      else:
        l = m + 1

    return -1 if l == kMax + 1 else l

  def _dfs(
      self,
      reversedGraph: list[list[tuple]],
      u: int,
      maxWeight: int,
      seen: set[int]
  ) -> int:
    """Returns the number of nodes reachable from u with weight <= maxWeight."""
    res = 1
    seen.add(u)
    for v, w in reversedGraph[u]:
      if w > maxWeight or v in seen:
        continue
      res += self._dfs(reversedGraph, v, maxWeight, seen)
    return res
 # code by PROGIEZ