LeetCode 3419 - Minimize the Maximum Edge Weight of Graph

LeetCode Problem 3419

Difficulty: 🟡 Medium
Topics: Binary Search, Depth-First Search, Breadth-First Search, Graph Theory, Shortest Path

Solution

Problem Understanding

The problem is asking us to manipulate a directed weighted graph in order to minimize the maximum edge weight while satisfying two constraints: every node must be able to reach node 0, and no node may have more outgoing edges than a given threshold. The input consists of:

n: the number of nodes labeled from 0 to n-1.
edges: a list of [source, target, weight] triples representing the directed edges of the graph.
threshold: the maximum allowed number of outgoing edges for any node.

The expected output is the minimum possible maximum edge weight after removing edges while still satisfying the connectivity and threshold constraints, or -1 if it is impossible.

Key points to notice:

Node 0 must be reachable from all other nodes, meaning we are essentially looking for a spanning subgraph directed towards node 0.
Each node cannot exceed threshold outgoing edges, which restricts the edge selection.
The goal is to minimize the largest edge weight used in the final subgraph.
Edge weights are all positive integers and there may be multiple edges between nodes, but with unique weights.

Important edge cases include scenarios where:

Some nodes have insufficient edges to connect to node 0 without violating the threshold.
Multiple edges between the same nodes force careful selection based on weight.
Small graphs where removing even one edge may make node 0 unreachable.

The constraints indicate that n can go up to 10^5 and edges can also scale up to roughly 10^5, so any solution must be near linear or linearithmic.

Approaches

A brute-force approach would enumerate all possible subsets of edges that satisfy the threshold constraint and connectivity, then select the one minimizing the maximum weight. This approach is infeasible because the number of edge subsets grows exponentially, making it impossible for the input size.

The key insight for an optimal solution is that the problem is a decision problem over edge weights. If we define a candidate maximum weight W, we can ask: "Is it possible to remove edges heavier than W and satisfy the connectivity and threshold constraints?" If yes, we can try a smaller W; if not, we must try a larger W. This naturally leads to a binary search on edge weights. To check each candidate weight efficiently, we can build a subgraph of edges ≤ W and perform a reachability check from node 0 in the reversed graph while enforcing the threshold constraint by pruning edges greedily per node.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^E * (DFS/BFS))	O(E+V)	Enumerate all edge subsets, prune invalid ones
Optimal	O(E log(maxWeight) + E log E)	O(E+V)	Binary search on maximum weight, BFS/DFS for connectivity, greedy pruning per node

Algorithm Walkthrough

Sort edges: We start by sorting edges by weight to efficiently check candidate maximum weights during binary search.
Binary search setup: Initialize low as the minimum edge weight and high as the maximum edge weight in the graph.
Binary search iteration: For each middle value mid between low and high, check if it is feasible:
Build a subgraph of edges where weight ≤ mid.
For each node, if the number of outgoing edges exceeds threshold, keep only the threshold smallest edges and discard the rest.
Reverse the subgraph edges so we can check reachability from node 0 efficiently.
Perform BFS or DFS from node 0 in the reversed subgraph. If all nodes are visited, mid is feasible; otherwise, it is not.
Update search bounds: If mid is feasible, record it as a candidate result and set high = mid - 1. Otherwise, set low = mid + 1.
Return the result: After binary search finishes, if a feasible maximum weight was found, return it. If no feasible solution exists, return -1.

Why it works: The binary search ensures that we find the minimum possible maximum edge weight efficiently. The greedy pruning ensures that the threshold constraint is respected, and reversing the graph ensures that reachability to node 0 is correctly verified.

Python Solution

from collections import defaultdict, deque
from typing import List

class Solution:
    def minMaxWeight(self, n: int, edges: List[List[int]], threshold: int) -> int:
        # Helper to check if max_weight is feasible
        def can_form(max_weight: int) -> bool:
            graph = defaultdict(list)
            for u, v, w in edges:
                if w <= max_weight:
                    graph[u].append((w, v))
            
            # Enforce threshold constraint
            for u in graph:
                graph[u].sort()  # sort by weight
                graph[u] = [v for _, v in graph[u][:threshold]]
            
            # BFS/DFS in reversed graph to check if all nodes can reach 0
            reverse_graph = defaultdict(list)
            for u in graph:
                for v in graph[u]:
                    reverse_graph[v].append(u)
            
            visited = [False] * n
            queue = deque([0])
            visited[0] = True
            while queue:
                node = queue.popleft()
                for neighbor in reverse_graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
            
            return all(visited)
        
        if not edges:
            return -1
        
        low, high = 1, max(w for _, _, w in edges)
        result = -1
        
        while low <= high:
            mid = (low + high) // 2
            if can_form(mid):
                result = mid
                high = mid - 1
            else:
                low = mid + 1
        
        return result

Explanation: The function can_form builds the feasible subgraph for a candidate maximum weight, prunes excess outgoing edges per threshold, and checks reachability to node 0 using BFS. Binary search iterates over possible weights efficiently to find the minimal feasible weight.

Go Solution

package main

import (
    "container/list"
    "sort"
)

func minMaxWeight(n int, edges [][]int, threshold int) int {
    canForm := func(maxWeight int) bool {
        graph := make([][]int, n)
        temp := make([][][]int, n)
        
        for _, e := range edges {
            u, v, w := e[0], e[1], e[2]
            if w <= maxWeight {
                temp[u] = append(temp[u], []int{w, v})
            }
        }
        
        for u := 0; u < n; u++ {
            sort.Slice(temp[u], func(i, j int) bool { return temp[u][i][0] < temp[u][j][0] })
            limit := threshold
            if len(temp[u]) < threshold {
                limit = len(temp[u])
            }
            for i := 0; i < limit; i++ {
                graph[u] = append(graph[u], temp[u][i][1])
            }
        }
        
        // Build reversed graph
        revGraph := make([][]int, n)
        for u := 0; u < n; u++ {
            for _, v := range graph[u] {
                revGraph[v] = append(revGraph[v], u)
            }
        }
        
        visited := make([]bool, n)
        queue := list.New()
        queue.PushBack(0)
        visited[0] = true
        
        for queue.Len() > 0 {
            elem := queue.Front()
            node := elem.Value.(int)
            queue.Remove(elem)
            for _, neighbor := range revGraph[node] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue.PushBack(neighbor)
                }
            }
        }
        
        for _, v := range visited {
            if !v {
                return false
            }
        }
        return true
    }
    
    if len(edges) == 0 {
        return -1
    }
    
    low, high := 1, 0
    for _, e := range edges {
        if e[2] > high {
            high = e[2]
        }
    }
    
    result := -1
    for low <= high {
        mid := (low + high) / 2
        if canForm(mid) {
            result = mid
            high = mid - 1
        } else {
            low = mid + 1
        }
    }
    
    return result
}

Explanation: The Go implementation mirrors the Python logic. Slices are used for adjacency lists, and a linked list implements BFS queue. Sorting ensures that threshold constraints are respected per node.

Worked Examples

Example 1

n = 5, edges = [[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]], threshold = 2

Binary search range: 1 to 2

mid = 1 → edges ≤1: [[1,0,1],[3,0,1],[4,3,1],[2,1,1]]. Threshold respected. Reverse graph