We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize the Maximum Edge Weight of Graph

Number: 3720

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a directed, weighted graph with n nodes and a list of edges, remove some edges (possibly none) so that:

  • Node 0 is reachable from every other node (i.e. for every node there exists a directed path to node 0).
  • The maximum edge weight among the remaining edges is minimized.
  • Each node has at most threshold outgoing edges in the remaining graph.

Return the minimum possible value of the maximum edge weight if such a subgraph exists, otherwise return -1.

Key Insights

  • The connectivity requirement (every node must reach node 0) can be checked by reversing the graph and ensuring that starting from node 0 all nodes are reached.
  • The degree constraint (each node has at most threshold outgoing edges) is automatically satisfied by choosing a spanning arborescence since every node (except 0) will use exactly one outgoing edge.
  • With a fixed maximum allowed edge weight X, we can discard all edges with weight more than X and then check if the remaining (reversed) graph is connected from node 0.
  • Using binary search over the range of edge weights efficiently determines the smallest maximum weight for which a valid subgraph exists.

Space and Time Complexity

Time Complexity: O(E * log(W)) where E is the number of edges and W is the range of edge weights.
Space Complexity: O(n + E) for storing the graph.

Solution

We solve the problem with binary search combined with a graph connectivity check:

  1. Define low and high as the minimum and maximum edge weights.
  2. For a given candidate mid value, consider only edges with weight <= mid.
  3. Reverse these edges (since connectivity from every node to 0 in the original is equivalent to 0 reaching every node in the reversed graph).
  4. Perform a DFS/BFS from node 0 in the reversed graph and see if all nodes are visited.
  5. If all nodes are reachable then mid is feasible and we try a smaller mid, otherwise, we need to allow larger edge weights.
  6. Return the smallest mid for which connectivity is achieved.
    Since a spanning arborescence can be constructed (each node except 0 needing at most one outgoing edge) the threshold constraint is naturally satisfied as threshold ≥ 1.

Code Solutions

# Python solution with detailed comments
from collections import deque

def minimizeMaxEdge(n, edges, threshold):
    # Extract possible weight bounds
    low = min(w for _, _, w in edges)
    high = max(w for _, _, w in edges)
    
    # Helper function: check connectivity in reversed graph (from 0 reaching all nodes)
    def canReachAll(max_weight):
        # Build reversed graph using only edges with weight <= max_weight
        rev_graph = [[] for _ in range(n)]
        for u, v, w in edges:
            if w <= max_weight:
                # Reverse the edge: v -> u
                rev_graph[v].append(u)
        # BFS/DFS starting from node 0
        seen = [False] * n
        queue = deque([0])
        seen[0] = True
        while queue:
            curr = queue.popleft()
            for neighbor in rev_graph[curr]:
                if not seen[neighbor]:
                    seen[neighbor] = True
                    queue.append(neighbor)
        return all(seen)
    
    result = -1
    # Binary search for the minimum maximum edge weight that yields connectivity
    while low <= high:
        mid = (low + high) // 2
        if canReachAll(mid):
            result = mid
            high = mid - 1  # Try a smaller maximum weight
        else:
            low = mid + 1   # Increase the allowed edge weight
    
    return result

# Example usage:
if __name__ == "__main__":
    n = 5
    edges = [[1,0,1],[2,0,2],[3,0,1],[4,3,1],[2,1,1]]
    threshold = 2
    print(minimizeMaxEdge(n, edges, threshold))  # Expected 1
← Back to All Questions