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.
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.
Python
Java
C++
Go
TypeScript
| 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 |
Practice Minimum Cost to Repair Edges to Traverse a Graph with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor