There is an undirected weighted graph with n nodes labeled from 0 to n - 1.
The graph is represented by a 2D integer array edges, where each edge edges[i] = [ui, vi, wi] indicates that there is an undirected edge between nodes ui and vi with weight wi.
You are also given integers source, target and k.
A threshold value determines whether an edge is considered light or heavy:
An edge is light if its weight is less than or equal to threshold.
An edge is heavy if its weight is greater than threshold.
A path from source to target is valid if it contains at most k heavy edges.
Return the minimum integer threshold such that at least one valid path exists from source to target. If no such path exists, return -1.
Example 1:
Input: n = 6, edges = [[0,1,5],[1,2,3],[3,4,4],[4,5,1],[1,4,2]], source = 0, target = 3, k = 1
Output: 4
Explanation:
The minimum threshold such that a path from node 0 to node 3 uses at most 1 heavy edge is 4.
Light edges: [1, 2, 3], [3, 4, 4], [4, 5, 1], [1, 4, 2]
Heavy edges: [0, 1, 5]
A valid path is 0 → 1 → 4 → 3. It uses only 1 heavy edge ([0, 1, 5]), which satisfies the limit k = 1.
Any smaller threshold would make it impossible to reach node 3 without exceeding 1 heavy edge.
Example 2:
Input: n = 6, edges = [[0,1,3],[1,2,4],[3,4,5],[4,5,6]], source = 0, target = 4, k = 1
Output: -1
Explanation:
There is no path from node 0 to node 4. Since the target cannot be reached, the output is -1.
Example 3:
Input: n = 4, edges = [[0,1,2],[1,2,2],[2,3,2],[3,0,2]], source = 0, target = 0, k = 0
Output: 0
Explanation:
The source and target are the same node. No edges need to be traversed, so the minimum threshold is 0.
Constraints:
1 <= n <= 1030 <= edges.length <= 103edges[i] = [ui, vi, wi]0 <= ui, vi <= n - 11 <= wi <= 1090 <= source, target <= n - 10 <= k <= edges.lengthProblem Overview: You are given a weighted graph and a limit on how many heavy edges a path can use. The goal is to travel from the source to the destination while minimizing the maximum allowed weight threshold. Any edge whose weight exceeds this threshold counts as a heavy edge, and the path may contain at most k of them.
Approach 1: Brute Force Path Enumeration (Exponential time, O(V) space)
The most direct strategy is to explore all possible paths from source to destination using DFS or backtracking. For every candidate path, compute the threshold value and count how many edges exceed it. Keep the minimum threshold among paths that use at most k heavy edges. This works only for very small graphs because the number of paths grows exponentially with vertices. The method mainly helps clarify the constraint: you are trading off between threshold size and number of heavy edges.
Approach 2: Dijkstra With State Tracking (O(E log V * K) time, O(V * K) space)
A better solution treats the problem as a shortest path variant. Extend the state to (node, heavyUsed). When you traverse an edge, check whether its weight exceeds the current candidate threshold and update the heavy edge counter. A priority queue similar to shortest path algorithms like Dijkstra can explore states while tracking the minimum threshold encountered so far. Each node can appear with multiple heavy-edge counts, so the state space becomes V * (K + 1). This approach handles general graphs but is heavier than necessary when the threshold itself can be searched directly.
Approach 3: Binary Search on Threshold + 0-1 BFS (O(E log W) time, O(V) space)
The key observation: the answer is the smallest threshold T such that a path exists using at most k edges with weight greater than T. Instead of computing the threshold during traversal, binary search the value of T. For each candidate threshold, convert the graph into a cost model: edges with weight ≤ T cost 0, and edges with weight > T cost 1. Now the task becomes finding the minimum number of heavy edges from source to destination. A graph traversal using 0-1 BFS efficiently solves this in O(E). If the minimum heavy-edge count ≤ k, the threshold is feasible. Combine this with binary search over edge weights to obtain the smallest valid threshold.
Recommended for interviews: The binary search + 0-1 BFS approach is the expected solution. It separates the optimization variable (threshold) from the feasibility check. Brute force demonstrates understanding of the constraint, but the optimized method shows strong algorithmic reasoning with monotonic search and efficient graph traversal.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS / Path Enumeration | Exponential | O(V) | Only for tiny graphs or conceptual understanding |
| Dijkstra with (node, heavyUsed) state | O(E log V * K) | O(V * K) | General solution when directly modeling constraints |
| Binary Search + 0-1 BFS | O(E log W) | O(V) | Optimal approach when threshold monotonicity exists |
Practice Minimum Threshold Path With Limited Heavy Edges with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor