LeetCode Problem 3620

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Graph Theory, Topological Sort, Heap (Priority Queue), Shortest Path

Solution

LeetCode 3620 - Network Recovery Pathways

Problem Understanding

We are given a directed acyclic graph (DAG) with n nodes numbered from 0 to n - 1.

Each directed edge is represented as:

u -> v with cost c

and stored in:

edges[i] = [u, v, c]

We are also given a boolean array online, where:

online[i] = True  => node i can be used
online[i] = False => node i is offline

The problem guarantees that node 0 and node n - 1 are always online.

A path from node 0 to node n - 1 is considered valid if:

1. Every intermediate node on the path is online.
2. The sum of all edge costs along the path is at most k.

For every valid path, we define:

score(path) = minimum edge cost appearing on that path

Among all valid paths, we want the largest possible score.

Equivalently, we are looking for a path whose weakest edge is as large as possible, while also satisfying the total cost constraint and avoiding offline intermediate nodes.

If no valid path exists, we return -1.

What the Constraints Tell Us

The constraints are large:

n <= 5 * 10^4
m <= 10^5
cost <= 10^9
k <= 5 * 10^13

This immediately rules out enumerating paths. Even in a DAG, the number of paths can be exponential.

The graph being acyclic is the key structural property. DAGs allow dynamic programming and topological processing in linear time.

Important Edge Cases

A valid implementation must handle several tricky situations.

If there is no path from 0 to n - 1, the answer is -1.

If every path passes through an offline intermediate node, the answer is also -1.

The best bottleneck path may exceed the cost limit k, so maximizing the minimum edge alone is insufficient.

Edge costs may be zero, meaning the answer can legitimately be 0.

Because k can reach 5 * 10^13, all accumulated path costs must be stored in 64-bit integers.

Approaches

Brute Force

A brute force solution would enumerate every path from node 0 to node n - 1.

For each path:

1. Verify all intermediate nodes are online.
2. Compute total cost.
3. Compute the minimum edge cost on the path.
4. If total cost is at most k, update the answer.

This is correct because every possible path is examined.

Unfortunately, even in a DAG, the number of paths can be exponential. A graph with many branching choices can contain an enormous number of distinct paths.

Therefore, path enumeration is completely infeasible for the given limits.

Key Insight

The objective is:

maximize(minimum edge on path)

This form strongly suggests binary search on the answer.

Suppose we guess a score value X.

We ask:

Is there a valid path from 0 to n-1 such that

1. every edge on the path has cost >= X
2. total path cost <= k
3. all intermediate nodes are online?

If such a path exists, then score X is achievable.

If score X is achievable, then every smaller value is also achievable.

This monotonicity makes binary search possible.

The remaining challenge is checking feasibility for a fixed threshold X.

When X is fixed:

Keep only edges with cost >= X.

Now we need the minimum possible total cost from 0 to n - 1 in this filtered DAG.

If that minimum cost is at most k, then threshold X is feasible.

Since the graph is a DAG, shortest path can be computed using dynamic programming in topological order in:

O(n + m)

time.

Thus we obtain an efficient solution:

Binary Search + DAG Shortest Path

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(path length)	Enumerates all paths
Optimal	O((n + m) log C)	O(n + m)	Binary search on bottleneck value, DAG DP for feasibility

Here C is the maximum edge cost.

Algorithm Walkthrough

1. Build the DAG

Construct an adjacency list from the edge list.

At the same time, compute indegrees for topological sorting.

2. Compute a Topological Order

Since the graph is guaranteed to be acyclic, Kahn's algorithm produces a valid topological order.

This order will later allow shortest path computation in linear time.

3. Binary Search on the Answer

The answer must be one of the edge costs.

Let:

low = 0
high = maximum edge cost

Binary search for the largest feasible threshold.

4. Feasibility Check for Threshold X

For a candidate score X:

Create a DP array:

dist[i] = minimum total cost to reach node i

Initialize:

dist[0] = 0
dist[others] = INF

Process nodes in topological order.

For every edge:

u -> v with cost c

ignore it if:

c < X

because using such an edge would make the path score less than X.

Also reject transitions into offline intermediate nodes:

v != n-1 and online[v] == False

For every remaining edge:

dist[v] = min(dist[v], dist[u] + c)

After processing all nodes:

dist[n-1]

is the minimum possible total cost among all paths whose edges are at least X.

If:

dist[n-1] <= k

then threshold X is feasible.

5. Update Binary Search

If threshold X is feasible:

answer = X
low = X + 1

Otherwise:

high = X - 1

6. Return the Answer

If no threshold is feasible, return -1.

Otherwise return the largest feasible threshold found.

Why it Works

For any threshold X, the feasibility test computes the minimum total cost among all paths whose every edge has cost at least X. Because the graph is a DAG, dynamic programming in topological order correctly computes shortest paths.

If this minimum cost is at most k, then there exists a valid path with score at least X. If not, no such path exists.

Feasibility is monotone: if score X is achievable, then every score smaller than X is also achievable. Therefore binary search finds the largest achievable score.

Python Solution

from typing import List
from collections import deque

class Solution:
    def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
        n = len(online)

        if not edges:
            return -1

        graph = [[] for _ in range(n)]
        indegree = [0] * n

        max_cost = 0

        for u, v, cost in edges:
            graph[u].append((v, cost))
            indegree[v] += 1
            max_cost = max(max_cost, cost)

        queue = deque(i for i in range(n) if indegree[i] == 0)
        topo = []

        while queue:
            u = queue.popleft()
            topo.append(u)

            for v, _ in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)

        INF = 10**30

        def feasible(threshold: int) -> bool:
            dist = [INF] * n
            dist[0] = 0

            for u in topo:
                if dist[u] == INF:
                    continue

                for v, cost in graph[u]:
                    if cost < threshold:
                        continue

                    if v != n - 1 and not online[v]:
                        continue

                    new_cost = dist[u] + cost

                    if new_cost < dist[v]:
                        dist[v] = new_cost

            return dist[n - 1] <= k

        if not feasible(0):
            return -1

        left = 0
        right = max_cost
        answer = 0

        while left <= right:
            mid = (left + right) // 2

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

        return answer

Implementation Explanation

The graph is first converted into an adjacency list, and a topological ordering is generated using Kahn's algorithm.

The nested feasible() function performs the core check. Given a threshold, it ignores every edge whose cost is smaller than that threshold. This effectively restricts attention to paths whose minimum edge cost is at least the threshold.

The shortest path within this filtered graph is computed using dynamic programming over the topological order. Since every edge is processed exactly once, the computation is linear in the graph size.

Binary search repeatedly invokes this feasibility test. Whenever a threshold is feasible, we attempt a larger threshold. Otherwise we search lower values. The final answer is the largest feasible threshold.

Go Solution

package main

func findMaxPathScore(edges [][]int, online []bool, k int64) int {
	n := len(online)

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

	graph := make([][][2]int, n)
	indegree := make([]int, n)

	maxCost := 0

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

		graph[u] = append(graph[u], [2]int{v, cost})
		indegree[v]++

		if cost > maxCost {
			maxCost = cost
		}
	}

	queue := make([]int, 0)

	for i := 0; i < n; i++ {
		if indegree[i] == 0 {
			queue = append(queue, i)
		}
	}

	topo := make([]int, 0, n)

	for head := 0; head < len(queue); head++ {
		u := queue[head]
		topo = append(topo, u)

		for _, edge := range graph[u] {
			v := edge[0]

			indegree[v]--

			if indegree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}

	const INF int64 = 1 << 60

	feasible := func(threshold int) bool {
		dist := make([]int64, n)

		for i := range dist {
			dist[i] = INF
		}

		dist[0] = 0

		for _, u := range topo {
			if dist[u] == INF {
				continue
			}

			for _, edge := range graph[u] {
				v := edge[0]
				cost := edge[1]

				if cost < threshold {
					continue
				}

				if v != n-1 && !online[v] {
					continue
				}

				newCost := dist[u] + int64(cost)

				if newCost < dist[v] {
					dist[v] = newCost
				}
			}
		}

		return dist[n-1] <= k
	}

	if !feasible(0) {
		return -1
	}

	left, right := 0, maxCost
	answer := 0

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

		if feasible(mid) {
			answer = mid
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return answer
}

Go Specific Notes

The total path cost may exceed 32-bit integer limits, therefore int64 is used for all distance calculations and for k.

The adjacency list stores destination and cost as a fixed-size array [2]int, which avoids additional struct definitions and keeps the implementation compact.

Worked Examples

Example 1

edges =
[[0,1,5],
 [1,3,10],
 [0,2,3],
 [2,3,4]]

k = 10

Topological order:

[0,1,2,3]

Binary search checks threshold 5.

Allowed edges:

0->1 (5)
1->3 (10)

DP progression:

Node	Dist Before	Updates
0	0	dist[1]=5
1	5	dist[3]=15
2	INF	none
3	15	none

Result:

dist[3] = 15 > 10

Threshold 5 fails.

Check threshold 3.

Allowed edges:

0->1 (5)
1->3 (10)
0->2 (3)
2->3 (4)

DP:

Node	Dist Before	Updates
0	0	dist[1]=5, dist[2]=3
1	5	dist[3]=15
2	3	dist[3]=7
3	7	none

Result:

dist[3] = 7 <= 10

Threshold 3 succeeds.

Final answer:

3

Example 2

online = [T,T,T,F,T]

Node 3 is offline.

Threshold 6:

Allowed edges:

0->1 (7)
0->2 (6)
2->4 (6)

The edge through node 3 is ignored because node 3 is offline.

DP:

Node	Dist
0	0
1	7
2	6
4	12

Since:

12 <= k

threshold 6 succeeds.

Threshold 7 fails because path:

0->1->4

contains edge cost 5.

Therefore the answer is:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) log C)	Binary search performs O(log C) feasibility checks
Space	O(n + m)	Graph, indegree array, topological order, and DP array

The topological order is computed once in O(n + m) time. Each feasibility check scans every node and edge exactly once, also requiring O(n + m) time. Since binary search performs O(log C) checks where C is the maximum edge cost, the overall complexity becomes O((n + m) log C).

Test Cases

sol = Solution()

assert sol.findMaxPathScore(
    [[0,1,5],[1,3,10],[0,2,3],[2,3,4]],
    [True, True, True, True],
    10
) == 3  # example 1

assert sol.findMaxPathScore(
    [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]],
    [True, True, True, False, True],
    12
) == 6  # example 2

assert sol.findMaxPathScore(
    [],
    [True, True],
    0
) == -1  # no edges

assert sol.findMaxPathScore(
    [[0,1,5]],
    [True, True],
    4
) == -1  # path exists but exceeds k

assert sol.findMaxPathScore(
    [[0,1,0]],
    [True, True],
    0
) == 0  # zero-cost edge

assert sol.findMaxPathScore(
    [[0,1,10],[1,2,10]],
    [True, False, True],
    100
) == -1  # only path uses offline intermediate node

assert sol.findMaxPathScore(
    [[0,1,8],[1,3,8],[0,2,5],[2,3,5]],
    [True, True, True, True],
    20
) == 8  # choose stronger bottleneck

assert sol.findMaxPathScore(
    [[0,1,1000000000]],
    [True, True],
    1000000000
) == 1000000000  # maximum edge cost

assert sol.findMaxPathScore(
    [[0,1,3],[1,3,3],[0,2,10],[2,3,10]],
    [True, True, True, True],
    6
) == 3  # high-score path too expensive

assert sol.findMaxPathScore(
    [[0,1,2],[1,2,2],[2,3,2]],
    [True, True, True, True],
    6
) == 2  # exact k boundary

Test Summary

Test	Why
Example 1	Verifies basic bottleneck optimization under cost constraint
Example 2	Verifies offline node filtering
Empty edge list	No path exists
Cost exceeds k	Reachable destination but invalid path
Zero-cost edge	Confirms answer can be zero
Offline intermediate node	Ensures offline nodes invalidate paths
Multiple valid paths	Chooses largest bottleneck
Maximum edge cost	Verifies binary search range
Strong path too expensive	Cost constraint overrides bottleneck
Exact k boundary	Confirms <= k handling

Edge Cases

One important edge case occurs when no path exists from node 0 to node n - 1. A common bug is returning 0 because binary search starts at zero. The implementation prevents this by first checking whether threshold 0 is feasible. If even threshold 0 fails, the function immediately returns -1.

Another important case involves offline intermediate nodes. A path may appear valid when looking only at edges and costs, yet become invalid because it passes through an offline node. During every relaxation step, the algorithm explicitly rejects transitions into offline nodes unless that node is the destination n - 1.

A third important case is when the best bottleneck path exceeds the budget k. Many solutions that focus only on maximizing the minimum edge would incorrectly choose such a path. The feasibility check instead computes the minimum total cost among all paths satisfying the threshold, ensuring the budget constraint is enforced simultaneously.

A final subtle case involves very large values of k and edge costs. Path sums can reach tens of trillions, which exceeds 32-bit integer limits. Both implementations store path distances using 64-bit capable types, Python integers in Python and int64 in Go, ensuring no overflow occurs.