You are given a directed acyclic graph of n nodes numbered from 0 to n − 1. This is represented by a 2D array edges of length m, where edges[i] = [ui, vi, costi] indicates a one‑way communication from node ui to node vi with a recovery cost of costi.
Some nodes may be offline. You are given a boolean array online where online[i] = true means node i is online. Nodes 0 and n − 1 are always online.
A path from 0 to n − 1 is valid if:
k.For each valid path, define its score as the minimum edge‑cost along that path.
Return the maximum path score (i.e., the largest minimum-edge cost) among all valid paths. If no valid path exists, return -1.
Example 1:
Input: edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10
Output: 3
Explanation:
The graph has two possible routes from node 0 to node 3:
Path 0 → 1 → 3
Total cost = 5 + 10 = 15, which exceeds k (15 > 10), so this path is invalid.
Path 0 → 2 → 3
Total cost = 3 + 4 = 7 <= k, so this path is valid.
The minimum edge‐cost along this path is min(3, 4) = 3.
There are no other valid paths. Hence, the maximum among all valid path‐scores is 3.
Example 2:
Input: edges = [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]], online = [true,true,true,false,true], k = 12
Output: 6
Explanation:
Node 3 is offline, so any path passing through 3 is invalid.
Consider the remaining routes from 0 to 4:
Path 0 → 1 → 4
Total cost = 7 + 5 = 12 <= k, so this path is valid.
The minimum edge‐cost along this path is min(7, 5) = 5.
Path 0 → 2 → 3 → 4
Node 3 is offline, so this path is invalid regardless of cost.
Path 0 → 2 → 4
Total cost = 6 + 6 = 12 <= k, so this path is valid.
The minimum edge‐cost along this path is min(6, 6) = 6.
Among the two valid paths, their scores are 5 and 6. Therefore, the answer is 6.
Constraints:
n == online.length2 <= n <= 5 * 1040 <= m == edges.length <= min(105, n * (n - 1) / 2)edges[i] = [ui, vi, costi]0 <= ui, vi < nui != vi0 <= costi <= 1090 <= k <= 5 * 1013online[i] is either true or false, and both online[0] and online[n − 1] are true.Problem Overview: You are given a network of nodes and connections representing recovery routes after failures. The task is to determine valid recovery pathways that satisfy shortest-path constraints while respecting dependency order between nodes.
Approach 1: Brute Force Graph Traversal (Exponential time, O(V) space)
The most direct idea is to enumerate every possible path from the source to the destination using DFS. For each path, compute the total cost and verify whether it satisfies the recovery constraints. This approach repeatedly explores the same subpaths and becomes infeasible once the graph grows beyond small sizes. Time complexity grows exponentially with the number of nodes because the algorithm explores all combinations of routes, while recursion depth requires O(V) stack space.
Approach 2: Dijkstra + Shortest Path DAG + Dynamic Programming (O(E log V) time, O(V + E) space)
The optimal strategy first computes the shortest distance from the source to every node using Dijkstra's algorithm with a min heap. After distances are known, keep only edges that maintain the shortest path condition dist[u] + w = dist[v]. These edges form a Directed Acyclic Graph (shortest-path DAG). Once this DAG is built, process nodes in topological order and use dynamic programming to count or evaluate valid recovery pathways. Each node aggregates results from its predecessors, avoiding recomputation. This approach leverages shortest path algorithms and efficient heap operations, giving O(E log V) time and linear graph storage.
Approach 3: Binary Search on Constraint + Shortest Path Check (O(log C * (E log V)) time)
If the problem introduces a constraint such as maximum delay or recovery threshold, you can binary search on the allowed value. For each candidate threshold, run a constrained shortest-path or feasibility check that ignores edges violating the constraint. This pattern combines binary search with graph traversal. It works well when the answer lies within a numeric range and feasibility is monotonic.
Recommended for interviews: Interviewers expect the Dijkstra + shortest-path DAG + DP approach. Brute force shows understanding of graph traversal, but the optimal solution demonstrates control over priority queues, shortest path properties, and DP on DAGs using topological ordering.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS Path Enumeration | O(2^V) | O(V) | Useful only for very small graphs or understanding the search space |
| Dijkstra + Shortest Path DAG + DP | O(E log V) | O(V + E) | General case; optimal solution for large graphs with weighted edges |
| Binary Search + Shortest Path Feasibility | O(log C * (E log V)) | O(V + E) | When the answer depends on a monotonic threshold such as time, delay, or capacity |
3620. Network Recovery Pathways | Binary Search | Dijkstra • Tech Courses • 600 views views
Watch 9 more video solutions →Practice Network Recovery Pathways with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor