Minimum Cost to Repair Edges to Traverse a Graph solution and explanation
The problem
You are given an undirected graph with n nodes labeled from 0 to n - 1. The graph consists of m edges represented by a 2D integer array edges, where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with a repair cost of wi.
You are also given an integer k. Initially, all edges are damaged.
You may choose a non-negative integer money and repair all edges whose repair cost is less than or equal to money. All other edges remain damaged and cannot be used.
You want to travel from node 0 to node n - 1 using at most k edges.
Return an integer denoting the minimum amount of money required to make this possible, or return -1 if it is impossible.
Example 1:
Input: n = 3, edges = [[0,1,10],[1,2,10],[0,2,100]], k = 1
Output: 100
Explanation:
The only valid path using at most k = 1 edge is 0 -> 2, which requires repairing the edge with cost 100. Therefore, the minimum required amount of money is 100.
Example 2:
Input: n = 6, edges = [[0,2,5],[2,3,6],[3,4,7],[4,5,5],[0,1,10],[1,5,12],[0,3,9],[1,2,8],[2,4,11]], k = 2
Output: 12
Explanation:
- With
money = 12, all edges with repair cost at most 12 become usable. - This allows the path
0 -> 1 -> 5, which uses exactly 2 edges and reaches node 5. - If
money < 12, there is no available path of length at mostk = 2from node 0 to node 5. - Therefore, the minimum required money is 12.
Example 3:
Input: n = 3, edges = [[0,1,1]], k = 1
Output: -1
Explanation:
It is impossible to reach node 2 from node 0 using any amount of money. Therefore, the answer is -1.
Constraints:
2 <= n <= 5 * 1041 <= edges.length == m <= 105edges[i] = [ui, vi, wi]0 <= ui, vi < n1 <= wi <= 1091 <= k <= n- There are no self-loops or duplicate edges in the graph.
Approach overview
Problem Overview: You are given a graph where some edges require a repair cost before they can be used. The goal is to determine the minimum cost threshold that allows you to traverse the graph between required nodes. Instead of repairing every edge, you only want to allow edges whose repair cost is within the smallest possible limit that still keeps the graph connected.
Approach 1: Cost Enumeration + BFS (Brute Force) (Time: O(K * (V + E)), Space: O(V))
Collect all unique repair costs and try them one by one as the allowed maximum repair cost. For each candidate cost c, run a Breadth-First Search from the start node and only traverse edges whose repair cost is ≤ c. If the destination (or all required nodes) becomes reachable, that cost works. The smallest working cost is the answer. This approach is simple but inefficient because BFS may run many times—once for every candidate repair cost.
Approach 2: Binary Search + BFS (Optimal) (Time: O((V + E) log C), Space: O(V))
The key observation: if the graph becomes traversable with repair cost c, it will also remain traversable for any cost greater than c. This monotonic property allows you to apply Binary Search on the repair cost range. For a midpoint value mid, run a BFS traversal and only follow edges whose repair cost ≤ mid. If BFS successfully reaches the target nodes, reduce the search range; otherwise increase it. Each feasibility check is a standard graph traversal using an adjacency list from graph representation.
The algorithm works as follows: build the adjacency list, set the search bounds using the minimum and maximum repair cost, and repeatedly binary search on this range. For every candidate threshold, run BFS to verify reachability. Because BFS runs in linear graph time and binary search cuts the search space logarithmically, the overall runtime becomes efficient even for large graphs.
Recommended for interviews: Binary Search + BFS is the expected solution. The brute force enumeration demonstrates understanding of the feasibility check, but the optimized version shows you recognize the monotonic property and can combine binary search with graph traversal to reduce repeated work.
Solution
We observe that the higher the repair cost, the more edges become available, making it easier to satisfy the requirement of reaching node n - 1 from node 0 using at most k edges. Moreover, the minimum repair cost must be among the costs in edges. Therefore, we first sort edges by repair cost, then use binary search to find the minimum repair cost that satisfies the requirement.
We perform binary search on the index of the repair cost, defining the left boundary as l = 0 and the right boundary as r = |edges| - 1. For the middle position mid = \lfloor (l + r) / 2 \rfloor, we add all edges with repair cost less than or equal to edges[mid][2] to the graph, then use BFS to determine whether we can reach node n - 1 from node 0 using at most k edges. If possible, we update the right boundary to r = mid; otherwise, we update the left boundary to l = mid + 1. After the binary search completes, we need to perform one more BFS to check if edges[l][2] satisfies the requirement. If it does, we return edges[l][2]; otherwise, we return -1.
The time complexity is O((m + n) times log m) and the space complexity is O(n), where n and m are the number of nodes and edges, respectively.
class Solution:
def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
def check(idx: int) -> bool:
g = [[] for _ in range(n)]
for u, v, _ in edges[: idx + 1]:
g[u].append(v)
g[v].append(u)
q = [0]
dist = 0
vis = [False] * n
vis[0] = True
while q:
nq = []
for u in q:
if u == n - 1:
return dist <= k
for v in g[u]:
if not vis[v]:
vis[v] = True
nq.append(v)
q = nq
dist += 1
return False
m = len(edges)
edges.sort(key=lambda x: x[2])
l, r = 0, m - 1
while l < r:
mid = (l + r) >> 1
if check(mid):
r = mid
else:
l = mid + 1
return edges[l][2] if check(l) else -1class Solution {
private int n;
private int[][] edges;
private int k;
public int minCost(int n, int[][] edges, int k) {
this.n = n;
this.edges = edges;
this.k = k;
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
int l = 0, r = edges.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return check(l) ? edges[l][2] : -1;
}
private boolean check(int idx) {
List<Integer>[] g = new List[n];
Arrays.setAll(g, i -> new ArrayList<>());
for (int i = 0; i <= idx; ++i) {
int u = edges[i][0], v = edges[i][1];
g[u].add(v);
g[v].add(u);
}
List<Integer> q = new ArrayList<>();
q.add(0);
int dist = 0;
boolean[] vis = new boolean[n];
vis[0] = true;
while (!q.isEmpty()) {
List<Integer> nq = new ArrayList<>();
for (int u : q) {
if (u == n - 1) {
return dist <= k;
}
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
nq.add(v);
}
}
}
q = nq;
++dist;
}
return false;
}
}class Solution {
public:
int minCost(int n, vector<vector<int>>& edges, int k) {
sort(edges.begin(), edges.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
auto check = [&](int idx) -> bool {
vector<vector<int>> g(n);
for (int i = 0; i <= idx; ++i) {
int u = edges[i][0], v = edges[i][1];
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> q;
q.push_back(0);
vector<char> vis(n, 0);
vis[0] = 1;
int dist = 0;
while (!q.empty()) {
vector<int> nq;
for (int u : q) {
if (u == n - 1) {
return dist <= k;
}
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = 1;
nq.push_back(v);
}
}
}
q.swap(nq);
++dist;
}
return false;
};
int m = edges.size();
int l = 0, r = m - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return check(l) ? edges[l][2] : -1;
}
};function minCost(n: number, edges: number[][], k: number): number {
edges.sort((a, b) => a[2] - b[2]);
const check = (idx: number): boolean => {
const g: number[][] = Array.from({ length: n }, () => []);
for (let i = 0; i <= idx; i++) {
const [u, v] = edges[i];
g[u].push(v);
g[v].push(u);
}
let q: number[] = [0];
const vis: boolean[] = Array(n).fill(false);
vis[0] = true;
let dist = 0;
while (q.length > 0) {
const nq: number[] = [];
for (const u of q) {
if (u === n - 1) {
return dist <= k;
}
for (const v of g[u]) {
if (!vis[v]) {
vis[v] = true;
nq.push(v);
}
}
}
q = nq;
dist++;
}
return false;
};
let [l, r] = [0, edges.length - 1];
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return check(l) ? edges[l][2] : -1;
}func minCost(n int, edges [][]int, k int) int {
sort.Slice(edges, func(i, j int) bool {
return edges[i][2] < edges[j][2]
})
check := func(idx int) bool {
g := make([][]int, n)
for i := 0; i <= idx; i++ {
u, v := edges[i][0], edges[i][1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
q := make([]int, 0, n)
q = append(q, 0)
vis := make([]bool, n)
vis[0] = true
dist := 0
for len(q) > 0 {
nq := make([]int, 0)
for _, u := range q {
if u == n-1 {
return dist <= k
}
for _, v := range g[u] {
if !vis[v] {
vis[v] = true
nq = append(nq, v)
}
}
}
q = nq
dist++
}
return false
}
m := len(edges)
l, r := 0, m-1
for l < r {
mid := (l + r) >> 1
if check(mid) {
r = mid
} else {
l = mid + 1
}
}
if check(l) {
return edges[l][2]
}
return -1
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Cost Enumeration + BFS | O(K * (V + E)) | O(V) | Useful for understanding feasibility checks or when the number of unique repair costs is very small |
| Binary Search + BFS | O((V + E) log C) | O(V) | Best general solution when repair costs vary widely and the graph is large |
Frequently asked questions
Is Minimum Cost to Repair Edges to Traverse a Graph easy or hard?
The problem is typically classified as Medium difficulty. The BFS traversal itself is straightforward, but recognizing the monotonic property that enables binary search over repair costs requires stronger algorithmic intuition.
Minimum Cost to Repair Edges to Traverse a Graph Python/Java solution
The standard implementation builds an adjacency list and runs BFS inside a binary search loop. This approach works consistently across Python, Java, C++, Go, and TypeScript because it relies on basic graph traversal and numeric search operations.
What is the best approach for Minimum Cost to Repair Edges to Traverse a Graph?
Binary Search combined with BFS is the most efficient approach. Binary search is applied on the repair cost threshold, and BFS checks whether the graph remains traversable using edges with cost less than or equal to that threshold. This reduces repeated graph traversal and results in O((V + E) log C) time complexity.
How to solve Minimum Cost to Repair Edges to Traverse a Graph in O((V+E) log C)?
Binary search the minimum repair cost threshold and use BFS as a feasibility check. For each midpoint cost, traverse the graph and only use edges whose repair cost is less than or equal to that value. If the destination or required nodes are reachable, move the search to the lower half; otherwise search higher costs.
Is Minimum Cost to Repair Edges to Traverse a Graph asked at Google/Amazon/Meta?
Graph reachability combined with binary search on constraints appears frequently in interviews at companies like Google, Amazon, and Meta. Variants include minimum maximum edge weight, connectivity under constraints, and feasibility checks using BFS or DFS.
What data structure is used in Minimum Cost to Repair Edges to Traverse a Graph?
The solution uses an adjacency list to represent the graph and a queue for BFS traversal. Binary search is applied on the repair cost range, while a visited set or boolean array tracks explored nodes during BFS.
What is the time complexity of Minimum Cost to Repair Edges to Traverse a Graph?
The optimal Binary Search + BFS approach runs in O((V + E) log C) time, where V is the number of vertices, E is the number of edges, and C is the range of repair costs. Each binary search step performs a BFS traversal that scans the graph once.