Skip to main content
Talentd

Network Recovery Pathways - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingGraph12 min readAsked at: Amazon, Bloomberg
Practice this problem

Problem Statement

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:

  • All intermediate nodes on the path are online.
  • The total recovery cost of all edges on the path does not exceed 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:

    1. Path 0 → 1 → 3

      • Total cost = 5 + 10 = 15, which exceeds k (15 > 10), so this path is invalid.

    2. 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:

    1. 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.

    2. Path 0 → 2 → 3 → 4

      • Node 3 is offline, so this path is invalid regardless of cost.

    3. 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.length
  • 2 <= n <= 5 * 104
  • 0 <= m == edges.length <= min(105, n * (n - 1) / 2)
  • edges[i] = [ui, vi, costi]
  • 0 <= ui, vi < n
  • ui != vi
  • 0 <= costi <= 109
  • 0 <= k <= 5 * 1013
  • online[i] is either true or false, and both online[0] and online[n − 1] are true.
  • The given graph is a directed acyclic graph.

Approach Overview

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.

Solution

The path score is defined as the minimum edge cost along the path. We seek the maximum score among all valid paths.

For a candidate minimum edge weight mid, we only keep edges with cost at least mid, then check whether there exists a path from node 0 to node n - 1 with total cost at most k. This reduces to running heap-optimized Dijkstra on the filtered graph.

As mid increases, fewer edges remain and feasibility becomes harder to satisfy, so we can binary search on mid. We preprocess by removing edges incident to offline nodes, and set l and r to the minimum and maximum edge costs. If check(l) is true, return l; otherwise return -1.

The time complexity is O((n + m) log n log W), and the space complexity is O(n + m), where n and m are the numbers of nodes and edges, and W is the maximum edge cost.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS Path EnumerationO(2^V)O(V)Useful only for very small graphs or understanding the search space
Dijkstra + Shortest Path DAG + DPO(E log V)O(V + E)General case; optimal solution for large graphs with weighted edges
Binary Search + Shortest Path FeasibilityO(log C * (E log V))O(V + E)When the answer depends on a monotonic threshold such as time, delay, or capacity

Video Solution

Network Recovery Pathways | Detailed Explanation | Simplified | Leetcode 3620 | codestorywithMIK • codestorywithMIK • 8,717 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Network Recovery Pathways easy or hard?
Network Recovery Pathways is considered a Hard problem because it combines multiple advanced concepts: shortest path algorithms, heap-based priority queues, dynamic programming on DAGs, and sometimes binary search on constraints.
Network Recovery Pathways Python/Java solution
Typical implementations use Dijkstra with a heap to compute shortest distances, then perform DP on edges that maintain the shortest-path condition. The same logic translates directly to Python (heapq), Java (PriorityQueue), C++, and Go using adjacency lists and arrays.
How to solve Network Recovery Pathways in O(E log V)?
Run Dijkstra from the source node to compute the shortest distance to every node. Construct a DAG containing only edges that satisfy dist[u] + w = dist[v]. Then apply dynamic programming in topological order to count or compute valid recovery pathways.
What is the best approach for Network Recovery Pathways?
The most efficient solution uses Dijkstra's shortest path algorithm followed by dynamic programming on a shortest-path DAG. After computing minimum distances with a priority queue, keep only edges that preserve shortest distances and process them using topological order. This reduces redundant exploration and runs in O(E log V) time.
Is Network Recovery Pathways asked at Google/Amazon/Meta?
Hard graph problems involving shortest paths, priority queues, and DAG dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often involve counting shortest paths or processing nodes in topological order after running Dijkstra.
What data structure is used in Network Recovery Pathways?
Key structures include adjacency lists for the graph, a min-heap (priority queue) for Dijkstra's algorithm, and arrays or hash maps for storing distances and DP values. Topological sorting is used when processing the shortest-path DAG.
What is the time complexity of Network Recovery Pathways?
The optimal algorithm runs in O(E log V) time due to the priority queue operations in Dijkstra's algorithm. Building the shortest-path DAG and running DP over it takes O(V + E). Space complexity is also O(V + E) for storing graph edges and DP states.

Ready to solve this problem?

Practice Network Recovery Pathways with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays