LeetCode 3807 - Minimum Cost to Repair Edges to Traverse a Graph

LeetCode Problem 3807

Difficulty: 🟡 Medium
Topics: Binary Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem presents an undirected graph with n nodes labeled from 0 to n-1 and m edges. Each edge has a repair cost, and initially, all edges are damaged. We can spend a certain amount of money to repair all edges whose cost is less than or equal to that amount. After repairing some edges, we want to determine if it is possible to travel from node 0 to node n-1 using at most k edges, and we need to find the minimum amount of money that allows this traversal. If it is impossible to reach the destination under the given constraints, we return -1.

The input edges is a list of [u, v, w], representing an edge between nodes u and v with a repair cost w. The integer k is a strict upper bound on the number of edges we can use in the path from node 0 to node n-1.

Constraints indicate the input can be very large (n up to 50,000 and m up to 100,000), so any brute-force path search enumerating all possible edge combinations would be too slow. The problem also guarantees no self-loops or duplicate edges, which simplifies the graph representation.

Important edge cases include:

• No path exists even if all edges are repaired.
• The minimum path uses exactly k edges, not fewer.
• Large repair costs requiring binary search to efficiently find the minimum required money.

Approaches

The brute-force approach would involve trying every subset of edges whose repair costs are below a chosen money and then using BFS or DFS to see if a valid path exists within k edges. This approach is correct in principle but computationally infeasible because the number of subsets grows exponentially with m. Even iterating through all possible money values naively (up to 10^9) would be prohibitively slow.

The key insight is that the minimum money required is bounded by the set of edge costs. If we sort all edge costs and use binary search on this sorted list, we can check for each candidate money value whether a path of at most k edges exists using BFS. BFS is efficient because it finds the shortest path in terms of edge count. This transforms the problem into a binary search over edge costs with a BFS check for each candidate, reducing time complexity drastically.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^m * (n + m))	O(n + m)	Enumerates all subsets of edges; infeasible for large m
Optimal	O((n + m) * log m)	O(n + m)	Binary search on unique edge costs, BFS to verify path within k edges

Algorithm Walkthrough

1. Extract all unique edge costs from the input edges and sort them in ascending order. These represent all possible money candidates.
2. Initialize binary search pointers left = 0 and right = len(costs) - 1.
3. While left <= right, compute mid = (left + right) // 2 and use BFS to check if there is a path from node 0 to node n-1 using at most k edges, considering only edges with repair cost ≤ costs[mid].
4. If BFS succeeds, update the answer to costs[mid] and continue searching for a potentially smaller value on the left half (right = mid - 1).
5. If BFS fails, discard this value and continue searching on the right half (left = mid + 1).
6. After binary search completes, return the smallest valid money value found, or -1 if no path exists.

Why it works: Binary search ensures we test the minimum candidate costs first, and BFS guarantees that we only accept money values that allow a path within k edges. The algorithm is correct because the solution space is monotonic: if a path is possible with a certain money, it is also possible with any higher money.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minCost(self, n: int, edges: List[List[int]], k: int) -> int:
        # Extract unique costs
        costs = sorted(set(w for _, _, w in edges))
        
        # Build adjacency list
        adj = [[] for _ in range(n)]
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))
        
        def can_reach(max_cost: int) -> bool:
            # BFS to check if n-1 is reachable within k edges using edges <= max_cost
            queue = deque([(0, 0)])  # node, edges_used
            visited = [float('inf')] * n
            visited[0] = 0
            while queue:
                node, used = queue.popleft()
                if node == n - 1 and used <= k:
                    return True
                if used == k:
                    continue
                for nei, cost in adj[node]:
                    if cost <= max_cost and used + 1 < visited[nei]:
                        visited[nei] = used + 1
                        queue.append((nei, used + 1))
            return False
        
        left, right = 0, len(costs) - 1
        answer = -1
        while left <= right:
            mid = (left + right) // 2
            if can_reach(costs[mid]):
                answer = costs[mid]
                right = mid - 1
            else:
                left = mid + 1
        return answer

Explanation: First, we collect all unique repair costs and sort them. The adjacency list stores all edges. The can_reach function uses BFS to explore reachable nodes within k edges, only traversing edges with a cost ≤ max_cost. Binary search identifies the minimum max_cost that allows a valid path.

Go Solution

package main

import (
    "container/list"
    "math"
    "sort"
)

func minCost(n int, edges [][]int, k int) int {
    costSet := make(map[int]struct{})
    adj := make([][][2]int, n)
    
    for _, e := range edges {
        u, v, w := e[0], e[1], e[2]
        adj[u] = append(adj[u], [2]int{v, w})
        adj[v] = append(adj[v], [2]int{u, w})
        costSet[w] = struct{}{}
    }
    
    costs := make([]int, 0, len(costSet))
    for w := range costSet {
        costs = append(costs, w)
    }
    sort.Ints(costs)
    
    canReach := func(maxCost int) bool {
        visited := make([]int, n)
        for i := range visited {
            visited[i] = math.MaxInt32
        }
        visited[0] = 0
        q := list.New()
        q.PushBack([2]int{0, 0}) // node, edges used
        for q.Len() > 0 {
            front := q.Remove(q.Front()).([2]int)
            node, used := front[0], front[1]
            if node == n-1 && used <= k {
                return true
            }
            if used == k {
                continue
            }
            for _, nei := range adj[node] {
                if nei[1] <= maxCost && used+1 < visited[nei[0]] {
                    visited[nei[0]] = used + 1
                    q.PushBack([2]int{nei[0], used + 1})
                }
            }
        }
        return false
    }
    
    left, right := 0, len(costs)-1
    answer := -1
    for left <= right {
        mid := (left + right) / 2
        if canReach(costs[mid]) {
            answer = costs[mid]
            right = mid - 1
        } else {
            left = mid + 1
        }
    }
    return answer
}

Go-specific notes: We use container/list for BFS instead of slices for O(1) pop from the front. math.MaxInt32 is used to initialize visited distances. Slices and maps manage adjacency lists and unique costs.

Worked Examples

Example 1: n = 3, edges = [[0,1,10],[1,2,10],[0,2,100]], k = 1

Sorted costs: [10, 100]

Binary search tests mid = 10 → path 0→2 not allowed because cost 100 > 10 → BFS fails.

Test mid = 100 → path 0→2 is possible → BFS succeeds.

Answer: 100.

Example 2: 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

Sorted costs: [5,6,7,8,9,10,11,12]

Binary search finds 12 as the minimum cost that allows path