LeetCode Problem 3924

Difficulty: 🔴 Hard
Topics: Binary Search, Breadth-First Search, Graph Theory

Solution

LeetCode 3924 - Minimum Threshold Path With Limited Heavy Edges

Problem Understanding

We are given an undirected weighted graph with n nodes and a list of weighted edges. We must travel from source to target.

The key concept in this problem is the definition of a threshold. Once a threshold is chosen, every edge is classified into one of two categories:

• Light edge: weight <= threshold
• Heavy edge: weight > threshold

A path is considered valid if it contains at most k heavy edges.

Our task is to find the smallest possible threshold for which at least one valid path exists from source to target.

Another way to think about the problem is this:

For a fixed threshold T, every edge contributes either:

• Cost 0 if its weight is at most T
• Cost 1 if its weight is greater than T

We then ask:

Can we reach target from source using at most k heavy edges?

If the answer is yes for some threshold T, it will also be yes for every larger threshold, because increasing the threshold can only convert heavy edges into light edges.

This monotonic property is the key observation that enables binary search.

What the Constraints Tell Us

The constraints are:

• n <= 1000
• edges.length <= 1000
• wi <= 10^9

The graph is relatively small. Even an O(E log E) or O(E log W) solution is easily acceptable.

However, brute-forcing every possible threshold from 0 to 10^9 is impossible.

The edge weights are large, but there are only at most 1000 distinct edge weights. This strongly suggests binary searching over the threshold value.

Important Edge Cases

One important edge case occurs when source == target. In that situation, we already start at the destination and need no edges at all. The minimum threshold is therefore 0.

Another edge case is a disconnected graph. If target is unreachable regardless of threshold, the answer must be -1.

A third edge case occurs when k is very large. In that case, even paths containing many heavy edges may be acceptable, potentially allowing a very small threshold.

Finally, graphs may contain cycles. Any correct solution must avoid repeatedly revisiting nodes inefficiently.

Approaches

Brute Force

A direct approach would be to try every possible threshold and determine whether a valid path exists.

For a fixed threshold, we can treat heavy edges as cost 1 and light edges as cost 0. Then we compute the minimum number of heavy edges required to reach every node.

If the minimum heavy-edge count to reach target is at most k, the threshold works.

The problem is deciding which thresholds to test. Since edge weights can be as large as 10^9, checking every integer threshold is infeasible.

Even restricting ourselves to all distinct edge weights still requires running a graph search up to 1000 times.

Key Insight

Suppose threshold T works.

Then every threshold larger than T must also work.

Why?

Because increasing the threshold can only change some heavy edges into light edges. It can never make a valid path worse.

This creates a monotonic property:

Threshold too small -> invalid
Threshold large enough -> valid

Therefore we can binary search for the smallest valid threshold.

The remaining challenge is implementing the feasibility test efficiently.

For a fixed threshold:

• Light edge contributes cost 0
• Heavy edge contributes cost 1

We need the minimum number of heavy edges from source to target.

This is exactly a 0-1 shortest path problem.

Using 0-1 BFS, we can compute the minimum heavy-edge count in O(V + E) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(E × (V + E))	O(V + E)	Check every distinct threshold individually
Optimal	O((V + E) log E)	O(V + E)	Binary search on threshold and use 0-1 BFS for feasibility

Algorithm Walkthrough

Optimal Algorithm

1. Handle the special case where source == target. Since no edges are needed, return 0.
2. Build an adjacency list representation of the graph. Each entry stores a neighboring node and the edge weight.
3. Collect all distinct edge weights and sort them.
4. Before performing binary search, check whether target is reachable at all. Run the feasibility test using a threshold equal to the maximum edge weight. In this situation every edge is light, so the test becomes a simple reachability check. If the target is still unreachable, return -1.
5. Define a feasibility function can(threshold).
6. Inside can(threshold), run a 0-1 BFS:

• Traversing a light edge adds cost 0.
• Traversing a heavy edge adds cost 1.
• Maintain dist[node], the minimum number of heavy edges needed to reach that node.

7. Use a deque:

• When traversing a light edge, push the neighbor to the front.
• When traversing a heavy edge, push the neighbor to the back.

8. After the BFS finishes, check whether dist[target] <= k.
9. Perform binary search over the sorted distinct edge weights:

• If can(weight[mid]) is true, search the left half.
• Otherwise search the right half.

10. The first threshold that passes the feasibility test is the answer.

Why it Works

For a fixed threshold, every path has a well-defined number of heavy edges. The 0-1 BFS computes the minimum possible heavy-edge count from source to every node.

Therefore can(T) returns true exactly when there exists a path from source to target containing at most k heavy edges.

Furthermore, if can(T) is true, then can(T') is also true for every T' > T, because increasing the threshold only reduces the number of heavy edges on every path.

Since the feasibility function is monotonic, binary search correctly finds the smallest threshold for which a valid path exists.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minimumThreshold(
        self,
        n: int,
        edges: List[List[int]],
        source: int,
        target: int,
        k: int
    ) -> int:

        if source == target:
            return 0

        if not edges:
            return -1

        graph = [[] for _ in range(n)]
        weights = set()

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
            weights.add(w)

        sorted_weights = sorted(weights)

        def can(threshold: int) -> bool:
            INF = float("inf")
            dist = [INF] * n
            dist[source] = 0

            dq = deque([source])

            while dq:
                node = dq.popleft()

                for nei, weight in graph[node]:
                    cost = 0 if weight <= threshold else 1
                    new_dist = dist[node] + cost

                    if new_dist < dist[nei]:
                        dist[nei] = new_dist

                        if cost == 0:
                            dq.appendleft(nei)
                        else:
                            dq.append(nei)

            return dist[target] <= k

        if not can(max(sorted_weights)):
            return -1

        left = 0
        right = len(sorted_weights) - 1
        answer = sorted_weights[right]

        while left <= right:
            mid = (left + right) // 2
            threshold = sorted_weights[mid]

            if can(threshold):
                answer = threshold
                right = mid - 1
            else:
                left = mid + 1

        return answer

Implementation Explanation

The adjacency list stores all graph edges in both directions because the graph is undirected.

The can() function performs a 0-1 BFS. The distance array stores the minimum number of heavy edges required to reach each node.

For every edge, we determine whether it is light or heavy relative to the current threshold. Light edges contribute cost 0, while heavy edges contribute cost 1.

A deque is used because 0-1 BFS exploits the fact that edge weights are only 0 or 1. Nodes reached through a zero-cost edge are processed immediately by inserting them at the front of the deque. Nodes reached through a one-cost edge are inserted at the back.

After computing the minimum heavy-edge count to reach every node, we simply check whether the target can be reached using at most k heavy edges.

The binary search operates on the sorted unique edge weights. Because feasibility is monotonic, the first threshold that succeeds is the minimum valid answer.

Go Solution

package main

import (
	"container/list"
	"sort"
)

func minimumThreshold(n int, edges [][]int, source int, target int, k int) int {
	if source == target {
		return 0
	}

	if len(edges) == 0 {
		return -1
	}

	type Edge struct {
		to int
		w  int
	}

	graph := make([][]Edge, n)
	weightSet := make(map[int]struct{})

	for _, e := range edges {
		u, v, w := e[0], e[1], e[2]

		graph[u] = append(graph[u], Edge{v, w})
		graph[v] = append(graph[v], Edge{u, w})

		weightSet[w] = struct{}{}
	}

	weights := make([]int, 0, len(weightSet))
	for w := range weightSet {
		weights = append(weights, w)
	}
	sort.Ints(weights)

	can := func(threshold int) bool {
		const INF = int(1e9)

		dist := make([]int, n)
		for i := range dist {
			dist[i] = INF
		}

		dist[source] = 0

		dq := list.New()
		dq.PushFront(source)

		for dq.Len() > 0 {
			front := dq.Front()
			node := front.Value.(int)
			dq.Remove(front)

			for _, edge := range graph[node] {
				cost := 1
				if edge.w <= threshold {
					cost = 0
				}

				newDist := dist[node] + cost

				if newDist < dist[edge.to] {
					dist[edge.to] = newDist

					if cost == 0 {
						dq.PushFront(edge.to)
					} else {
						dq.PushBack(edge.to)
					}
				}
			}
		}

		return dist[target] <= k
	}

	if !can(weights[len(weights)-1]) {
		return -1
	}

	left := 0
	right := len(weights) - 1
	answer := weights[right]

	for left <= right {
		mid := left + (right-left)/2

		if can(weights[mid]) {
			answer = weights[mid]
			right = mid - 1
		} else {
			left = mid + 1
		}
	}

	return answer
}

Go-Specific Notes

The Go solution uses container/list to implement the deque required by 0-1 BFS.

A map is used to gather distinct edge weights before sorting them. The distance array uses a large sentinel value (1e9) as infinity, which is sufficient because the maximum possible heavy-edge count is at most the number of edges.

The binary search logic is identical to the Python implementation.

Worked Examples

Example 1

n = 6
edges = [[0,1,5],[1,2,3],[3,4,4],[4,5,1],[1,4,2]]
source = 0
target = 3
k = 1

Distinct weights:

[1, 2, 3, 4, 5]

Binary search begins.

Check Threshold = 3

Edge	Cost
0-1 (5)	1
1-2 (3)	0
3-4 (4)	1
4-5 (1)	0
1-4 (2)	0

Minimum heavy-edge path:

0 -> 1 -> 4 -> 3

Heavy edges used:

(0,1) and (4,3)

Count:

2

Since 2 > k, threshold 3 fails.

Check Threshold = 4

Edge	Cost
0-1 (5)	1
1-2 (3)	0
3-4 (4)	0
4-5 (1)	0
1-4 (2)	0

Path:

0 -> 1 -> 4 -> 3

Heavy-edge count:

1

Since 1 <= k, threshold 4 succeeds.

Answer:

4

Example 2

n = 6
edges = [[0,1,3],[1,2,4],[3,4,5],[4,5,6]]

The graph contains two disconnected components:

0-1-2

3-4-5

Node 4 is unreachable from node 0 regardless of threshold.

Reachability test fails.

Answer:

-1

Example 3

source = 0
target = 0

No movement is required.

Minimum threshold:

0

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O((V + E) log E)	Binary search over distinct weights, each step runs a 0-1 BFS
Space	O(V + E)	Graph storage, distance array, and deque

The graph contains at most E distinct thresholds worth testing. Binary search reduces this to log E feasibility checks. Each feasibility check is a 0-1 BFS, which runs in linear time with respect to the graph size. Therefore the total complexity is O((V + E) log E).

Test Cases

sol = Solution()

assert sol.minimumThreshold(
    6,
    [[0,1,5],[1,2,3],[3,4,4],[4,5,1],[1,4,2]],
    0,
    3,
    1
) == 4  # official example 1

assert sol.minimumThreshold(
    6,
    [[0,1,3],[1,2,4],[3,4,5],[4,5,6]],
    0,
    4,
    1
) == -1  # disconnected graph

assert sol.minimumThreshold(
    4,
    [[0,1,2],[1,2,2],[2,3,2],[3,0,2]],
    0,
    0,
    0
) == 0  # source equals target

assert sol.minimumThreshold(
    2,
    [[0,1,10]],
    0,
    1,
    1
) == 1  # one heavy edge allowed

assert sol.minimumThreshold(
    2,
    [[0,1,10]],
    0,
    1,
    0
) == 10  # edge must become light

assert sol.minimumThreshold(
    3,
    [[0,1,5],[1,2,7]],
    0,
    2,
    2
) == 5  # both edges may remain heavy except weight 5 threshold

assert sol.minimumThreshold(
    3,
    [[0,1,5],[1,2,7]],
    0,
    2,
    1
) == 7  # only one heavy edge allowed

assert sol.minimumThreshold(
    5,
    [],
    0,
    4,
    0
) == -1  # no edges

assert sol.minimumThreshold(
    4,
    [[0,1,100],[1,2,1],[2,3,100]],
    0,
    3,
    1
) == 100  # both large edges must become light

assert sol.minimumThreshold(
    4,
    [[0,1,100],[1,2,1],[2,3,100]],
    0,
    3,
    2
) == 1  # two heavy edges allowed

Test Summary

Test	Why
Example 1	Verifies binary search finds threshold 4
Example 2	Verifies disconnected graph handling
Example 3	Verifies source equals target
Single edge, k=1	Heavy edge may remain heavy
Single edge, k=0	Edge must become light
Two-edge path, k=2	Multiple heavy edges allowed
Two-edge path, k=1	One edge must become light
Empty graph	No path exists
Two large edges, k=1	Both large edges cannot remain heavy
Two large edges, k=2	Small threshold becomes sufficient

Edge Cases

Source Equals Target

When the source and target are the same node, the optimal path contains zero edges. Since no edge classification matters, the smallest valid threshold is 0. Failing to handle this case separately could incorrectly return -1 when the graph contains no edges.

Disconnected Graph

The graph may not contain any path between source and target. In that situation, no threshold can possibly help because changing the threshold only affects edge classifications, not graph connectivity. The implementation detects this by running the feasibility check with the maximum edge weight and returns -1 if the target remains unreachable.

Very Large k

When k is large enough to allow every heavy edge on a path, the answer may be much smaller than the largest edge weight. The 0-1 BFS naturally handles this case because it computes the minimum heavy-edge count and simply checks whether that count is at most k.

Graphs With Cycles

Cycles can cause inefficient repeated processing in naive graph traversals. The implementation maintains the minimum heavy-edge count for every node and only updates a node when a strictly better value is found. This guarantees correctness and prevents infinite looping.

Multiple Edges With Identical Weights

Many edges may share the same weight. Binary searching over every integer threshold would be wasteful. The implementation stores only distinct edge weights and searches among them, reducing the search space while preserving correctness because the classification only changes when the threshold crosses an existing edge weight.