Watch the video solution for Minimum Cost to Repair Edges to Traverse a Graph, a medium level problem involving Binary Search, Breadth-First Search, Graph. This walkthrough by Code-Yao has 36 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
money = 12, all edges with repair cost at most 12 become usable.0 -> 1 -> 5, which uses exactly 2 edges and reaches node 5.money < 12, there is no available path of length at most k = 2 from node 0 to node 5.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 <= nProblem 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.
| 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 |