Watch 10 video solutions for Network Recovery Pathways, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by Tech Courses has 600 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |