Watch 10 video solutions for Reachable Nodes In Subdivided Graph, a hard level problem involving Graph, Heap (Priority Queue), Shortest Path. This walkthrough by Coding Decoded has 4,695 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an undirected graph (the "original graph") with n nodes labeled from 0 to n - 1. You decide to subdivide each edge in the graph into a chain of nodes, with the number of new nodes varying between each edge.
The graph is given as a 2D array of edges where edges[i] = [ui, vi, cnti] indicates that there is an edge between nodes ui and vi in the original graph, and cnti is the total number of new nodes that you will subdivide the edge into. Note that cnti == 0 means you will not subdivide the edge.
To subdivide the edge [ui, vi], replace it with (cnti + 1) new edges and cnti new nodes. The new nodes are x1, x2, ..., xcnti, and the new edges are [ui, x1], [x1, x2], [x2, x3], ..., [xcnti-1, xcnti], [xcnti, vi].
In this new graph, you want to know how many nodes are reachable from the node 0, where a node is reachable if the distance is maxMoves or less.
Given the original graph and maxMoves, return the number of nodes that are reachable from node 0 in the new graph.
Example 1:
Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3 Output: 13 Explanation: The edge subdivisions are shown in the image above. The nodes that are reachable are highlighted in yellow.
Example 2:
Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4 Output: 23
Example 3:
Input: edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5 Output: 1 Explanation: Node 0 is disconnected from the rest of the graph, so only node 0 is reachable.
Constraints:
0 <= edges.length <= min(n * (n - 1) / 2, 104)edges[i].length == 30 <= ui < vi < n0 <= cnti <= 1040 <= maxMoves <= 1091 <= n <= 3000Problem Overview: You get an undirected graph where every edge is subdivided into multiple intermediate nodes. Starting from node 0 with maxMoves, count how many original and newly created nodes you can reach without exceeding the move limit.
Approach 1: Dijkstra's Algorithm on Logical Subdivisions (O(E log V) time, O(V + E) space)
Instead of explicitly building all subdivided nodes, treat each edge weight as the number of subdivisions. Run Dijkstra’s algorithm from node 0 using a max heap or priority queue that tracks remaining moves. When you traverse an edge, you consume moves equal to the number of subdivisions plus one to reach the neighbor. Even if you cannot reach the neighbor fully, you can still count partial progress along the subdivided nodes. Maintain how many new nodes were used on each edge from both directions and cap it by the subdivision count.
This approach avoids constructing potentially huge graphs. The algorithm only processes original nodes while logically accounting for intermediate ones. Works well because shortest remaining distance naturally determines how far you can travel along each edge. Uses techniques from shortest path and heap (priority queue) problems.
Approach 2: Depth First Search with Logical Path Expansion (O(E * maxMoves) time, O(V + E) space)
Perform DFS from node 0 while tracking remaining moves. Each recursive step attempts to move along edges and consume subdivisions step by step. If the remaining moves cannot reach the next original node, count only the intermediate nodes along that edge. Maintain a visited structure for edges so subdivided nodes are not double-counted when reached from both sides.
This approach models traversal more directly but becomes inefficient when maxMoves is large. DFS may repeatedly explore similar states. Useful mainly for reasoning about how subdivided nodes contribute to the final count.
Approach 3: Dijkstra on Explicitly Built Subdivided Graph (O((V + S) log (V + S)) time, O(V + S) space)
Construct the full graph where each edge with n subdivisions becomes a chain of n intermediate nodes. After building the expanded graph, run standard Dijkstra from node 0 and count nodes with distance ≤ maxMoves. This makes the logic simple but the graph size becomes huge because the number of new nodes equals the sum of all subdivisions.
This version demonstrates correctness clearly but is impractical for large inputs. It shows why treating subdivisions logically instead of physically is a key optimization when solving graph problems with implicit nodes.
Approach 4: Breadth-First Search with Move Tracking (O(E * maxMoves) time, O(V + E) space)
BFS can simulate movement layer by layer while tracking remaining steps. Each transition consumes part of the move budget along subdivided edges. Similar to DFS, it must track how many intermediate nodes have already been counted from each side of an edge. Because BFS does not prioritize shorter paths like Dijkstra, it may explore inefficient states when the graph has varying subdivision counts.
Recommended for interviews: Dijkstra’s algorithm with logical subdivision tracking. It keeps the graph small, guarantees optimal exploration order, and handles partial edge traversal cleanly. Interviewers expect candidates to recognize that explicitly building the subdivided graph is infeasible and that shortest-path logic solves the move constraint efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm on Logical Subdivisions | O(E log V) | O(V + E) | Best general solution; handles large subdivision counts efficiently |
| Depth First Search with Logical Path Expansion | O(E * maxMoves) | O(V + E) | Conceptual exploration of reachable nodes when constraints are small |
| Dijkstra on Explicitly Built Subdivided Graph | O((V + S) log (V + S)) | O(V + S) | Educational approach when the subdivided graph size is manageable |
| Breadth-First Search with Move Tracking | O(E * maxMoves) | O(V + E) | Works for small graphs or uniform edge costs |