Skip to main content
Talentd

Reachable Nodes In Subdivided Graph - Solution & Explanation

HardGraphHeap (Priority Queue)Shortest Path17 min readAsked at: Google, PhonePe
Practice this problem

Problem Statement

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 == 3
  • 0 <= ui < vi < n
  • There are no multiple edges in the graph.
  • 0 <= cnti <= 104
  • 0 <= maxMoves <= 109
  • 1 <= n <= 3000

Approach Overview

Problem 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 1: Dijkstra's Algorithm on Logical Subdivisions

We treat the problem as a shortest path problem. Each edge between nodes in the original graph may be subdivided logically without explicitly constructing all new nodes. We can utilize Dijkstra's algorithm to calculate the shortest paths starting from node 0, considering edge subdivisions.

The function initializes a graph where each node points to a dictionary of its connected nodes treating cnt as weights for route expansion. This is reminiscent of representing weighted edges for pathfinding algorithms. We use a priority queue to maintain node distances akin to Dijkstra's algorithm, continually exploring until all reachable nodes are calculated within maxMoves.

Code

Python

Python

Complexity

Time Complexity: O(E + V log V), where E is the number of edges and V the number of vertices.
Space Complexity: O(E + V) for storing the graph and distances.

Try this approach in the editor →

Approach 2: Depth First Search with Logical Path Expansion

Instead of explicitly constructing the whole subdivided graph, we utilize a DFS strategy. By expanding paths logically through recursion and considering move limits, we can calculate the number of reachable nodes without extra space overhead.

This solution builds an adjacency list to represent the graph. It applies a DFS approach, where each node recursively attempts to visit connected nodes, tracking nodes reached using a set. Subdivisions are not created explicitly, and instead, logical path expansion is calculated by allowable traversal of each edge within given maxMoves.

Code

Python

Python

Complexity

Time Complexity: O(V + E), where V is the number of vertices and E the number of edges, as it involves visiting nodes and edges logically.
Space Complexity: O(V + E) for adjacency list and visited set.

Try this approach in the editor →

Approach 3: Dijkstra's Algorithm on Subdivided Graph

This approach involves using Dijkstra's algorithm to calculate the shortest distance from node 0 to all other nodes in the subdivided graph. The subdivision requires splitting each edge into a path with additional nodes. The priority queue maintains nodes sorted by distance, ensuring efficient processing of the shortest paths first.

This Python implementation uses a priority queue (heap) to perform a modified Dijkstra's algorithm. The graph is built with adjacency lists where each node's neighbor's distance is stored. As we traverse the graph, we count the nodes within reach (incrementing result res). The 'dist' dictionary keeps the shortest known distance to each node from the starting node, and 'used' tracks how many new nodes we reach in subdivided edges. Finally, we sum up these used nodes for each edge in the given edges list to get the total reachable node count.

Code

PythonJavaScriptC++

Python

JavaScript

C++

Complexity

Time Complexity: O(E + N log N), where E is the number of edges and N is the number of nodes due to priority queue operations.
Space Complexity: O(N + E), for storing graph, distance, and used nodes mappings.

Try this approach in the editor →

Approach 4: Alternative Approach - Breadth-First Search (BFS)

This approach employs BFS to explore the graph iteratively. Unlike Dijkstra, BFS is less concerned with path cost optimization and focuses on level-wise expansion. It's useful when all edge weights are equal. Here, edges must be handled considering additional costs per neighbor negotiation based on subdivided portions of the graph.

The Java solution explores combinations of reachable nodes using BFS. A queue is used to maintain exploration from the starting node iteratively. Each node's reachable distance is updated if a shorter path via a neighbor is discovered, counting reachable nodes based on the accumulated distance.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(E + N^2), due to BFS and operations at each node with the distance array update.
Space Complexity: O(N + E), capturing the adjacency list and additional structures like queue and distance array.

Try this approach in the editor →

Approach 5: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dijkstra's Algorithm on Logical Subdivisions

Time Complexity: O(E + V log V), where E is the number of edges and V the number of vertices.
Space Complexity: O(E + V) for storing the graph and distances.

Depth First Search with Logical Path Expansion

Time Complexity: O(V + E), where V is the number of vertices and E the number of edges, as it involves visiting nodes and edges logically.
Space Complexity: O(V + E) for adjacency list and visited set.

Dijkstra's Algorithm on Subdivided Graph

Time Complexity: O(E + N log N), where E is the number of edges and N is the number of nodes due to priority queue operations.
Space Complexity: O(N + E), for storing graph, distance, and used nodes mappings.

Alternative Approach - Breadth-First Search (BFS)

Time Complexity: O(E + N^2), due to BFS and operations at each node with the distance array update.
Space Complexity: O(N + E), capturing the adjacency list and additional structures like queue and distance array.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dijkstra's Algorithm on Logical SubdivisionsO(E log V)O(V + E)Best general solution; handles large subdivision counts efficiently
Depth First Search with Logical Path ExpansionO(E * maxMoves)O(V + E)Conceptual exploration of reachable nodes when constraints are small
Dijkstra on Explicitly Built Subdivided GraphO((V + S) log (V + S))O(V + S)Educational approach when the subdivided graph size is manageable
Breadth-First Search with Move TrackingO(E * maxMoves)O(V + E)Works for small graphs or uniform edge costs

Video Solution

Reachable Nodes In Subdivided Graph | Leetcode 882 | Live coding session • Coding Decoded • 4,860 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reachable Nodes In Subdivided Graph easy or hard?
Reachable Nodes In Subdivided Graph is classified as Hard. The challenge comes from realizing that explicitly creating all subdivided nodes is infeasible and that the correct solution requires combining Dijkstra’s algorithm with partial edge traversal accounting.
Reachable Nodes In Subdivided Graph Python or Java solution?
Most implementations use Dijkstra with a heap. Python solutions typically rely on heapq with adjacency lists, while Java uses PriorityQueue and C++ uses priority_queue. The algorithmic structure remains the same across languages with O(E log V) complexity.
How to solve Reachable Nodes In Subdivided Graph in O(E log V)?
Run Dijkstra from node 0 to compute the shortest distance to each original node. For every edge (u, v, n), calculate how many subdivided nodes can be reached from both endpoints using the remaining moves. The total reachable nodes equal reachable original nodes plus the minimum of n and the sum of partial traversals from u and v.
What is the best approach for Reachable Nodes In Subdivided Graph?
Dijkstra’s algorithm with logical subdivision tracking is the most efficient approach. Instead of building every intermediate node, treat the subdivision count as edge weight and compute the shortest distance from node 0. Then count how many subdivided nodes can be consumed from each edge based on remaining moves. The complexity is O(E log V).
Is Reachable Nodes In Subdivided Graph asked at Google/Amazon/Meta?
Reachable Nodes In Subdivided Graph is a Hard graph problem commonly used to test shortest-path reasoning and priority queue usage. Variants of this problem appear in interviews at companies like Google, Amazon, and Meta when evaluating advanced graph traversal and optimization skills.
What data structure is used in Reachable Nodes In Subdivided Graph?
The core data structure is a priority queue (heap) used in Dijkstra’s shortest path algorithm. An adjacency list stores the graph, and hash maps or arrays track distances and how many subdivided nodes are used along each edge.
What is the time complexity of Reachable Nodes In Subdivided Graph?
The optimal solution using Dijkstra’s algorithm runs in O(E log V) time and O(V + E) space. Each edge is processed through a priority queue while computing the maximum reachable distance within maxMoves. Additional bookkeeping tracks how many subdivided nodes are used per edge.

Ready to solve this problem?

Practice Reachable Nodes In Subdivided Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All People With Secret

Next

Paths in Maze That Lead to Same Room