Minimize the Maximum Edge Weight of Graph

Minimize the Maximum Edge Weight of Graph - Problem

Imagine you're designing a transportation network where all cities must be able to reach the capital (node 0), but you want to minimize the heaviest route needed. You're given a directed weighted graph with n nodes (0 to n-1) and a list of edges with weights.

Your challenge is to remove some edges from the graph such that:

Connectivity: Node 0 must be reachable from every other node
Efficiency: The maximum edge weight in the final graph is minimized
Constraint: Each node can have at most threshold outgoing edges

Return the minimum possible maximum edge weight after optimal edge removal, or -1 if impossible.

Example: With nodes [0,1,2], edges [[1,0,1], [2,0,2], [1,0,3]], and threshold=1, we can keep edges with weights 1 and 2, giving us a maximum weight of 2.

Input & Output

example_1.py — Basic Case

$ Input: n = 3, threshold = 2, edges = [[1,0,1], [2,0,2], [1,2,3]]

› Output: 2

💡 Note: We need all nodes to reach node 0. Keep edges [1,0,1] and [2,0,2] (weights 1,2). Node 1 reaches 0 directly, node 2 reaches 0 directly. Maximum edge weight is 2.

example_2.py — Threshold Constraint

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

› Output: 3

💡 Note: With threshold=1, each node can have at most 1 outgoing edge. We can use [3,0,1], [1,3,2], [2,0,3]. All nodes reach 0: 1→3→0, 2→0, 3→0. Maximum weight is 3.

example_3.py — Impossible Case

$ Input: n = 3, threshold = 1, edges = [[0,1,1], [0,2,2]]

› Output: -1

💡 Note: Node 0 has outgoing edges but we need nodes 1 and 2 to reach node 0. With only outgoing edges from node 0, nodes 1 and 2 cannot reach node 0.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ threshold ≤ n - 1
0 ≤ edges.length ≤ min(10⁵, n * (n - 1))
edges[i] = [A_i, B_i, W_i]
0 ≤ A_i, B_i ≤ n - 1
A_i ≠ B_i
1 ≤ W_i ≤ 10⁶
No duplicate edges between same pair of nodes

Visualization

Tap to expand

Understanding the Visualization

Identify Goal

All nodes must be able to reach node 0 (the emergency shelter)

Apply Constraints

Each node can maintain at most 'threshold' outgoing roads due to budget limits

Binary Search

Search for the minimum possible 'maximum difficulty level' needed

Greedy Selection

For each candidate difficulty, greedily choose the easiest roads

Verify Connectivity

Check if all neighborhoods can still reach the shelter

Key Takeaway

🎯 Key Insight: Binary search on the maximum edge weight combined with greedy selection of lightest edges ensures optimal connectivity while respecting threshold constraints.

Asked in

G Google 28 a Amazon 22 ⊞ Microsoft 18 f Meta 15

The optimal approach uses binary search on the answer combined with greedy edge selection. We search for the minimum possible maximum edge weight, and for each candidate weight, greedily select the lightest edges while respecting the threshold constraint. The key insight is that if we can achieve connectivity with maximum weight X, we can also achieve it with any weight > X, making binary search applicable.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Try All Combinations)	O(2^E * (V + E))	O(V + E)	Try all possible edge combinations and check connectivity
Binary Search + Greedy Selection (Optimal)	O(E log E + E log W * (V + E))	O(V + E)	Binary search on maximum edge weight with greedy edge selection

Brute Force (Try All Combinations) — Algorithm Steps

Generate all possible combinations of edges
For each combination, check threshold constraints
Verify that node 0 is reachable from all other nodes
Track the minimum of maximum edge weights across valid solutions

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible subsets of edges

Check Constraints

Verify threshold and connectivity requirements

Track Minimum

Keep the smallest maximum edge weight found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>

typedef struct {
    int *data;
    int size;
    int capacity;
} IntArray;

IntArray* createIntArray() {
    IntArray *arr = malloc(sizeof(IntArray));
    arr->data = malloc(10 * sizeof(int));
    arr->size = 0;
    arr->capacity = 10;
    return arr;
}

void addToIntArray(IntArray *arr, int val) {
    if (arr->size >= arr->capacity) {
        arr->capacity *= 2;
        arr->data = realloc(arr->data, arr->capacity * sizeof(int));
    }
    arr->data[arr->size++] = val;
}

typedef struct {
    bool valid;
    int maxWeight;
} Result;

Result canReachZero(int n, int threshold, int selectedEdges[][3], int numEdges) {
    IntArray **graph = malloc(n * sizeof(IntArray*));
    int *outDegree = calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        graph[i] = createIntArray();
    }
    
    int maxWeight = 0;
    for (int i = 0; i < numEdges; i++) {
        int a = selectedEdges[i][0];
        int b = selectedEdges[i][1];
        int w = selectedEdges[i][2];
        addToIntArray(graph[b], a); // Reverse edge
        outDegree[a]++;
        if (w > maxWeight) maxWeight = w;
    }
    
    // Check threshold constraint
    for (int i = 0; i < n; i++) {
        if (outDegree[i] > threshold) {
            Result result = {false, INT_MAX};
            return result;
        }
    }
    
    // BFS from node 0
    bool *visited = calloc(n, sizeof(bool));
    int *queue = malloc(n * sizeof(int));
    int front = 0, rear = 0;
    
    visited[0] = true;
    queue[rear++] = 0;
    
    while (front < rear) {
        int node = queue[front++];
        for (int i = 0; i < graph[node]->size; i++) {
            int neighbor = graph[node]->data[i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue[rear++] = neighbor;
            }
        }
    }
    
    int visitedCount = 0;
    for (int i = 0; i < n; i++) {
        if (visited[i]) visitedCount++;
    }
    
    Result result = {visitedCount == n, maxWeight};
    return result;
}

int minimizeMaxEdgeWeight(int n, int threshold, int edges[][3], int numEdges) {
    int minMaxWeight = INT_MAX;
    
    // Try all possible subsets
    for (int mask = 0; mask < (1 << numEdges); mask++) {
        int selectedEdges[numEdges][3];
        int selectedCount = 0;
        
        for (int i = 0; i < numEdges; i++) {
            if (mask & (1 << i)) {
                selectedEdges[selectedCount][0] = edges[i][0];
                selectedEdges[selectedCount][1] = edges[i][1];
                selectedEdges[selectedCount][2] = edges[i][2];
                selectedCount++;
            }
        }
        
        Result result = canReachZero(n, threshold, selectedEdges, selectedCount);
        if (result.valid && result.maxWeight < minMaxWeight) {
            minMaxWeight = result.maxWeight;
        }
    }
    
    return minMaxWeight == INT_MAX ? -1 : minMaxWeight;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^E * (V + E))

2^E combinations to try, each requiring O(V + E) connectivity check

✓ Linear Growth

Space Complexity

O(V + E)

Space for graph representation and DFS/BFS traversal

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Try All Combinations) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler