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.

Description Hints 3 Solution Video 12:14

3807. Minimum Cost to Repair Edges to Traverse a Graph

Medium55.6% acceptancePremium elsewhere, free here

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] = [u_i, v_i, w_i] indicates that there is an edge between nodes u_i and v_i with a repair cost of w_i.

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 * 10⁴
1 <= edges.length == m <= 10⁵
edges[i] = [u_i, v_i, w_i]
0 <= u_i, v_i < n
1 <= w_i <= 10⁹
1 <= k <= n
There are no self-loops or duplicate edges in the graph.

Topics

Hints open one at a time

Hint 1

Use binary search.

Hint 2

For a fixed value of money, check whether there exists a path from node 0 to node n - 1 that uses at most k edges.

Hint 3

Use binary search to find the smallest value of money that makes this possible.

12:14

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

3
[[0,1,10],[1,2,10],[0,2,100]]
1

Input

6
[[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]]
2

Input

3
[[0,1,1]]
1

Your code is saved on this device.Solution