Skip to main content
Talentd

Minimum Cost to Repair Edges to Traverse a Graph - Solution & Explanation

MediumPremiumFree on FleetCodeBinary SearchBreadth-First SearchGraph12 min read
Practice this problem

Problem Statement

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 most k = 2 from 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 * 104
  • 1 <= edges.length == m <= 105
  • edges[i] = [ui, vi, wi]
  • 0 <= ui, vi < n
  • 1 <= wi <= 109
  • 1 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Cost Enumeration + BFSO(K * (V + E))O(V)Useful for understanding feasibility checks or when the number of unique repair costs is very small
Binary Search + BFSO((V + E) log C)O(V)Best general solution when repair costs vary widely and the graph is large

Video Solution

leetcode 3807 Minimum Cost to Repair Edges to Traverse a Graph | bfs with constraint • Code-Yao • 36 views views

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.

Ready to solve this problem?

Practice Minimum Cost to Repair Edges to Traverse a Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Median of Two Sorted Arrays

Next

Search in Rotated Sorted Array