882. Reachable Nodes In Subdivided Graph

HardGraphShortest PathHeap (Priority Queue)

LeetCode ↗

Problem Editor Pattern Idea Example Code Complex Pitfalls

Problem Description

You have an undirected graph with n nodes labeled from 0 to n - 1. Each edge in this graph can be subdivided into a chain of smaller edges with new intermediate nodes.

The graph is given as a 2D array edges where each element edges[i] = [ui, vi, cnti] represents:

An edge between nodes ui and vi in the original graph
cnti is the number of new nodes that will be inserted to subdivide this edge

When you subdivide an edge [ui, vi] with cnti new nodes:

The original edge is replaced with (cnti + 1) new edges
cnti new nodes x1, x2, ..., xcnti are created
The new edges form a chain: [ui, x1], [x1, x2], [x2, x3], ..., [xcnti-1, xcnti], [xcnti, vi]

For example, if an edge [0, 1] has cnt = 2, it becomes: [0, x1], [x1, x2], [x2, 1] with two new intermediate nodes.

After creating this new graph with all the subdivided edges, you need to find how many nodes are reachable from node 0 within maxMoves steps. A node is considered reachable if the shortest distance from node 0 to that node is at most maxMoves.

The problem asks you to return the total count of reachable nodes, which includes:

Original nodes that can be reached within maxMoves steps
New intermediate nodes created during edge subdivision that can be reached within maxMoves steps

Given:

edges: The original graph edges with subdivision counts
maxMoves: The maximum number of steps allowed
n: The number of nodes in the original graph

Return: The total number of nodes reachable from node 0 in the new subdivided graph.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why BFS?

This problem maps to BFS through a short path in the full flowchart.

Run Dijkstra from node zero on the original graph, then for each edge add the reachable subdivided nodes from both endpoints, capped by the edge length.

Open in Flowchart

Intuition

The key insight is that we need to handle two types of nodes differently: the original nodes and the newly created intermediate nodes from edge subdivision.

For the original nodes, we can use Dijkstra's algorithm to find the shortest distance from node 0 to every other node. But here's the trick - when we subdivide an edge with cnt intermediate nodes, the edge weight becomes cnt + 1 (since we need cnt + 1 steps to traverse from one end to the other through all intermediate nodes).

Once we have the shortest distances to all original nodes, counting reachable original nodes is straightforward - any node with distance ≤ maxMoves is reachable.

The challenging part is counting the reachable intermediate nodes. Consider an edge [u, v] that was subdivided with cnt intermediate nodes. These intermediate nodes form a line between u and v. We can reach some of these intermediate nodes from two directions:

Starting from node 0, reaching u, then moving into the edge towards v
Starting from node 0, reaching v, then moving into the edge towards u

From node u, we can reach at most maxMoves - dist[u] steps into the edge (if we have moves left after reaching u). Similarly, from node v, we can reach at most maxMoves - dist[v] steps into the edge.

The total intermediate nodes we can reach on edge [u, v] is the minimum of:

The actual number of intermediate nodes (cnt)
The sum of nodes reachable from both ends (a + b), where:
- a = min(cnt, max(0, maxMoves - dist[u]))
- b = min(cnt, max(0, maxMoves - dist[v]))

We take the minimum because if a + b > cnt, it means we're counting some nodes from both directions, but the actual number of intermediate nodes is only cnt.

This approach elegantly handles all cases - whether we can reach the entire edge, only parts of it from one or both ends, or none at all.

Pattern Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Uses graphsNew to the pattern? This video gives an overview of graph algorithms.

New to patterns?Most interview problems reduce to a handful of patterns. This video covers the main eight.

Solution Approach

The implementation uses Dijkstra's algorithm with a min-heap to find shortest distances, followed by counting reachable nodes.

Step 1: Build the Graph

g = defaultdict(list)
for u, v, cnt in edges:
    g[u].append((v, cnt + 1))
    g[v].append((u, cnt + 1))

We create an adjacency list where each edge weight is cnt + 1 (the number of steps needed to traverse the subdivided edge). Since the graph is undirected, we add edges in both directions.

Step 2: Run Dijkstra's Algorithm

q = [(0, 0)]  # (distance, node)
dist = [0] + [inf] * (n - 1)
while q:
    d, u = heappop(q)
    for v, cnt in g[u]:
        if (t := d + cnt) < dist[v]:
            dist[v] = t
            heappush(q, (t, v))

Initialize a min-heap with (0, 0) - starting from node 0 with distance 0
Initialize distance array: dist[0] = 0 and all others to infinity
Process nodes in order of increasing distance
For each neighbor v of current node u, if we find a shorter path, update dist[v] and add to heap
Note: This implementation does not skip stale heap entries, so a node can be popped more than once. A stale pop cannot lower any distance, so the results are still correct; it only adds extra work

Step 3: Count Reachable Original Nodes

ans = sum(d <= maxMoves for d in dist)

Count all original nodes whose shortest distance from node 0 is at most maxMoves.

Step 4: Count Reachable Intermediate Nodes

for u, v, cnt in edges:
    a = min(cnt, max(0, maxMoves - dist[u]))
    b = min(cnt, max(0, maxMoves - dist[v]))
    ans += min(cnt, a + b)

For each original edge with cnt intermediate nodes:

a: Maximum intermediate nodes reachable from u side = min(cnt, max(0, maxMoves - dist[u]))
- We have maxMoves - dist[u] moves left after reaching u
- Can't go negative (hence max(0, ...))
- Can't exceed the actual number of intermediate nodes (hence min(cnt, ...))
b: Similarly for the v side
Total reachable on this edge = min(cnt, a + b)
- If a + b ≤ cnt: We can reach a nodes from u side and b from v side without overlap
- If a + b > cnt: The entire edge is reachable, so we count all cnt intermediate nodes

The algorithm runs in O(E log V) time for Dijkstra's algorithm plus O(E) for counting intermediate nodes, where E is the number of edges and V is the number of vertices.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

n = 4 (nodes: 0, 1, 2, 3)
edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]]
maxMoves = 10

Step 1: Build the Graph

After subdivision, each edge weight becomes cnt + 1:

Edge [0,1] with cnt=4 → weight = 5 (needs 5 moves to traverse)
Edge [1,2] with cnt=6 → weight = 7
Edge [0,2] with cnt=8 → weight = 9
Edge [1,3] with cnt=1 → weight = 2

The graph looks like:

    0 ---(5)--- 1 ---(2)--- 3
     \         /
      \       /
       (9)  (7)
         \ /
          2

Step 2: Run Dijkstra's Algorithm

Starting from node 0:

Process node 0 (dist=0):
- To node 1: dist[1] = 0 + 5 = 5
- To node 2: dist[2] = 0 + 9 = 9
Process node 1 (dist=5):
- To node 2: 5 + 7 = 12 > 9 (no update)
- To node 3: dist[3] = 5 + 2 = 7
Process node 3 (dist=7): no improvements
Process node 2 (dist=9): no improvements

Final distances: dist = [0, 5, 9, 7]

Step 3: Count Reachable Original Nodes

Nodes with distance ≤ 10:

Node 0: dist=0 ✓
Node 1: dist=5 ✓
Node 2: dist=9 ✓
Node 3: dist=7 ✓

All 4 original nodes are reachable. Count = 4.

Step 4: Count Reachable Intermediate Nodes

For edge [0,1] with 4 intermediate nodes:

From node 0: can go min(4, max(0, 10-0)) = min(4, 10) = 4 steps
From node 1: can go min(4, max(0, 10-5)) = min(4, 5) = 4 steps
Total: min(4, 4+4) = min(4, 8) = 4 intermediate nodes

For edge [1,2] with 6 intermediate nodes:

From node 1: can go min(6, max(0, 10-5)) = min(6, 5) = 5 steps
From node 2: can go min(6, max(0, 10-9)) = min(6, 1) = 1 step
Total: min(6, 5+1) = min(6, 6) = 6 intermediate nodes

For edge [0,2] with 8 intermediate nodes:

From node 0: can go min(8, max(0, 10-0)) = min(8, 10) = 8 steps
From node 2: can go min(8, max(0, 10-9)) = min(8, 1) = 1 step
Total: min(8, 8+1) = min(8, 9) = 8 intermediate nodes

For edge [1,3] with 1 intermediate node:

From node 1: can go min(1, max(0, 10-5)) = min(1, 5) = 1 step
From node 3: can go min(1, max(0, 10-7)) = min(1, 3) = 1 step
Total: min(1, 1+1) = min(1, 2) = 1 intermediate node

Final Answer:

Original nodes: 4
Intermediate nodes: 4 + 6 + 8 + 1 = 19
Total reachable nodes: 4 + 19 = 23

Solution Implementation

1class Solution:
2    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
3        # Build adjacency list representation of the graph
4        # Each edge has 'cnt' intermediate nodes, so total distance is cnt + 1
5        graph = defaultdict(list)
6        for start_node, end_node, intermediate_count in edges:
7            graph[start_node].append((end_node, intermediate_count + 1))
8            graph[end_node].append((start_node, intermediate_count + 1))
9      
10        # Initialize priority queue for Dijkstra's algorithm
11        # Format: (distance, node)
12        priority_queue = [(0, 0)]
13      
14        # Initialize distances array (distance from node 0 to all other nodes)
15        # dist[0] = 0 (starting node), all others initialized to infinity
16        distances = [0] + [float('inf')] * (n - 1)
17      
18        # Run Dijkstra's algorithm to find shortest distances from node 0
19        while priority_queue:
20            current_distance, current_node = heappop(priority_queue)
21          
22            # Explore neighbors of current node
23            for neighbor, edge_weight in graph[current_node]:
24                new_distance = current_distance + edge_weight
25              
26                # If we found a shorter path to the neighbor, update it
27                if new_distance < distances[neighbor]:
28                    distances[neighbor] = new_distance
29                    heappush(priority_queue, (new_distance, neighbor))
30      
31        # Count main nodes that are reachable within maxMoves
32        reachable_count = sum(distance <= maxMoves for distance in distances)
33      
34        # Count intermediate nodes on edges that can be reached
35        for start_node, end_node, intermediate_count in edges:
36            # Calculate how many intermediate nodes can be reached from start_node
37            reachable_from_start = min(intermediate_count, max(0, maxMoves - distances[start_node]))
38          
39            # Calculate how many intermediate nodes can be reached from end_node
40            reachable_from_end = min(intermediate_count, max(0, maxMoves - distances[end_node]))
41          
42            # Total intermediate nodes reached on this edge (cannot exceed the actual count)
43            reachable_count += min(intermediate_count, reachable_from_start + reachable_from_end)
44      
45        return reachable_count
46

1class Solution {
2    public int reachableNodes(int[][] edges, int maxMoves, int n) {
3        // Build adjacency list representation of the graph
4        // Each node stores list of [neighbor, distance to neighbor]
5        List<int[]>[] graph = new List[n];
6        Arrays.setAll(graph, index -> new ArrayList<>());
7      
8        // Convert edges to adjacency list
9        // Note: distance = subdivided nodes + 1 (to account for moving through subdivisions)
10        for (int[] edge : edges) {
11            int nodeU = edge[0];
12            int nodeV = edge[1];
13            int distance = edge[2] + 1;  // Number of subdivided nodes + 1
14          
15            graph[nodeU].add(new int[] {nodeV, distance});
16            graph[nodeV].add(new int[] {nodeU, distance});
17        }
18      
19        // Initialize distances array for Dijkstra's algorithm
20        int[] distances = new int[n];
21        Arrays.fill(distances, 1 << 30);  // Initialize with large value (infinity)
22        distances[0] = 0;  // Starting node has distance 0
23      
24        // Priority queue for Dijkstra's algorithm: [distance, node]
25        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
26        priorityQueue.offer(new int[] {0, 0});  // Start from node 0 with distance 0
27      
28        // Run Dijkstra's algorithm to find shortest distances
29        while (!priorityQueue.isEmpty()) {
30            int[] current = priorityQueue.poll();
31            int currentDistance = current[0];
32            int currentNode = current[1];
33          
34            // Check all neighbors of current node
35            for (int[] neighbor : graph[currentNode]) {
36                int neighborNode = neighbor[0];
37                int edgeDistance = neighbor[1];
38              
39                // If we found a shorter path to the neighbor, update it
40                if (currentDistance + edgeDistance < distances[neighborNode]) {
41                    distances[neighborNode] = currentDistance + edgeDistance;
42                    priorityQueue.offer(new int[] {distances[neighborNode], neighborNode});
43                }
44            }
45        }
46      
47        // Count reachable original nodes
48        int totalReachableNodes = 0;
49        for (int distance : distances) {
50            if (distance <= maxMoves) {
51                totalReachableNodes++;
52            }
53        }
54      
55        // Count reachable subdivided nodes on each edge
56        for (int[] edge : edges) {
57            int nodeU = edge[0];
58            int nodeV = edge[1];
59            int subdividedNodes = edge[2];  // Number of subdivided nodes on this edge
60          
61            // Calculate how many subdivided nodes can be reached from nodeU
62            int reachableFromU = Math.min(subdividedNodes, Math.max(0, maxMoves - distances[nodeU]));
63          
64            // Calculate how many subdivided nodes can be reached from nodeV
65            int reachableFromV = Math.min(subdividedNodes, Math.max(0, maxMoves - distances[nodeV]));
66          
67            // Total reachable subdivided nodes on this edge (avoiding double counting)
68            totalReachableNodes += Math.min(subdividedNodes, reachableFromU + reachableFromV);
69        }
70      
71        return totalReachableNodes;
72    }
73}
74

1class Solution {
2public:
3    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
4        // Build adjacency list representation of the graph
5        // Each edge has small nodes between two big nodes
6        using PairIntInt = pair<int, int>;
7        vector<vector<PairIntInt>> adjacencyList(n);
8      
9        for (const auto& edge : edges) {
10            int nodeU = edge[0];
11            int nodeV = edge[1];
12            int smallNodeCount = edge[2];
13            // Add 1 to represent the cost to traverse from one big node to another
14            int traversalCost = smallNodeCount + 1;
15          
16            adjacencyList[nodeU].emplace_back(nodeV, traversalCost);
17            adjacencyList[nodeV].emplace_back(nodeU, traversalCost);
18        }
19      
20        // Dijkstra's algorithm to find shortest distances from node 0
21        priority_queue<PairIntInt, vector<PairIntInt>, greater<PairIntInt>> minHeap;
22        minHeap.emplace(0, 0); // (distance, node)
23      
24        // Initialize distances with a large value
25        vector<int> shortestDistance(n, INT_MAX);
26        shortestDistance[0] = 0;
27      
28        // Standard Dijkstra's algorithm
29        while (!minHeap.empty()) {
30            auto [currentDistance, currentNode] = minHeap.top();
31            minHeap.pop();
32          
33            // Skip if we've already found a better path to this node
34            if (currentDistance > shortestDistance[currentNode]) {
35                continue;
36            }
37          
38            // Explore neighbors
39            for (const auto& [neighbor, edgeCost] : adjacencyList[currentNode]) {
40                int newDistance = currentDistance + edgeCost;
41              
42                if (newDistance < shortestDistance[neighbor]) {
43                    shortestDistance[neighbor] = newDistance;
44                    minHeap.emplace(newDistance, neighbor);
45                }
46            }
47        }
48      
49        // Count reachable big nodes
50        int reachableNodeCount = 0;
51        for (int distance : shortestDistance) {
52            if (distance <= maxMoves) {
53                reachableNodeCount++;
54            }
55        }
56      
57        // Count reachable small nodes on each edge
58        for (const auto& edge : edges) {
59            int nodeU = edge[0];
60            int nodeV = edge[1];
61            int smallNodesOnEdge = edge[2];
62          
63            // Calculate how many small nodes can be reached from nodeU
64            int reachableFromU = min(smallNodesOnEdge, 
65                                    max(0, maxMoves - shortestDistance[nodeU]));
66          
67            // Calculate how many small nodes can be reached from nodeV
68            int reachableFromV = min(smallNodesOnEdge, 
69                                    max(0, maxMoves - shortestDistance[nodeV]));
70          
71            // Total reachable small nodes on this edge (avoiding double counting)
72            reachableNodeCount += min(smallNodesOnEdge, reachableFromU + reachableFromV);
73        }
74      
75        return reachableNodeCount;
76    }
77};
78

1function reachableNodes(edges: number[][], maxMoves: number, n: number): number {
2    // Build adjacency list representation of the graph
3    // Each edge has small nodes between two big nodes
4    const adjacencyList: Array<Array<[number, number]>> = Array(n).fill(null).map(() => []);
5  
6    for (const edge of edges) {
7        const nodeU = edge[0];
8        const nodeV = edge[1];
9        const smallNodeCount = edge[2];
10        // Add 1 to represent the cost to traverse from one big node to another
11        const traversalCost = smallNodeCount + 1;
12      
13        adjacencyList[nodeU].push([nodeV, traversalCost]);
14        adjacencyList[nodeV].push([nodeU, traversalCost]);
15    }
16  
17    // Dijkstra's algorithm to find shortest distances from node 0
18    // Using a min heap implemented with array and sort
19    const minHeap: Array<[number, number]> = [[0, 0]]; // [distance, node]
20  
21    // Initialize distances with a large value
22    const shortestDistance: number[] = Array(n).fill(Number.MAX_SAFE_INTEGER);
23    shortestDistance[0] = 0;
24  
25    // Standard Dijkstra's algorithm
26    while (minHeap.length > 0) {
27        // Sort to maintain min heap property
28        minHeap.sort((a, b) => a[0] - b[0]);
29        const [currentDistance, currentNode] = minHeap.shift()!;
30      
31        // Skip if we've already found a better path to this node
32        if (currentDistance > shortestDistance[currentNode]) {
33            continue;
34        }
35      
36        // Explore neighbors
37        for (const [neighbor, edgeCost] of adjacencyList[currentNode]) {
38            const newDistance = currentDistance + edgeCost;
39          
40            if (newDistance < shortestDistance[neighbor]) {
41                shortestDistance[neighbor] = newDistance;
42                minHeap.push([newDistance, neighbor]);
43            }
44        }
45    }
46  
47    // Count reachable big nodes
48    let reachableNodeCount = 0;
49    for (const distance of shortestDistance) {
50        if (distance <= maxMoves) {
51            reachableNodeCount++;
52        }
53    }
54  
55    // Count reachable small nodes on each edge
56    for (const edge of edges) {
57        const nodeU = edge[0];
58        const nodeV = edge[1];
59        const smallNodesOnEdge = edge[2];
60      
61        // Calculate how many small nodes can be reached from nodeU
62        const reachableFromU = Math.min(
63            smallNodesOnEdge,
64            Math.max(0, maxMoves - shortestDistance[nodeU])
65        );
66      
67        // Calculate how many small nodes can be reached from nodeV
68        const reachableFromV = Math.min(
69            smallNodesOnEdge,
70            Math.max(0, maxMoves - shortestDistance[nodeV])
71        );
72      
73        // Total reachable small nodes on this edge (avoiding double counting)
74        reachableNodeCount += Math.min(smallNodesOnEdge, reachableFromU + reachableFromV);
75    }
76  
77    return reachableNodeCount;
78}
79

Time and Space Complexity

Time Complexity: O((E + V) * log V) where E is the number of edges and V is the number of vertices (n).

Building the adjacency list takes O(E) time as we iterate through all edges once.
The Dijkstra's algorithm implementation uses a min-heap. In the worst case, each edge can be relaxed once, leading to O(E) heap operations.
Each heap operation (push/pop) takes O(log E) time, since the heap can hold up to O(E) entries (one per successful relaxation). Because E ≤ V², log E = O(log V).
The final loop to count reachable nodes within edges takes O(E) time.
Therefore, the dominant operation is the Dijkstra's algorithm portion: O(E * log V).
Since we also iterate through vertices for initialization and counting, the total complexity is O((E + V) * log V).

Space Complexity: O(E + V)

The adjacency list graph stores all edges twice (bidirectional), requiring O(E) space.
The distance array distances requires O(V) space.
The priority queue can contain up to O(E) entries in the worst case, because a node may be pushed once per successful relaxation.
Overall space complexity is O(E + V).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Processing Stale Heap Entries

The solution above pushes a new heap entry each time a shorter distance is found, so older entries for the same node stay in the heap. When such a stale entry is popped, its distance is larger than distances[current_node].

while priority_queue:
    current_distance, current_node = heappop(priority_queue)
    for neighbor, edge_weight in graph[current_node]:
        new_distance = current_distance + edge_weight
        if new_distance < distances[neighbor]:
            distances[neighbor] = new_distance
            heappush(priority_queue, (new_distance, neighbor))

This does not produce wrong answers: relaxing from a stale entry uses a distance that is too large, so new_distance < distances[neighbor] fails for any neighbor whose distance is already correct. It does repeat work, scanning the neighbors of the same node more than once.

Optimization: Skip stale entries right after popping:

while priority_queue:
    current_distance, current_node = heappop(priority_queue)

    # Skip if we've already found a better path to this node
    if current_distance > distances[current_node]:
        continue

    for neighbor, edge_weight in graph[current_node]:
        new_distance = current_distance + edge_weight
        if new_distance < distances[neighbor]:
            distances[neighbor] = new_distance
            heappush(priority_queue, (new_distance, neighbor))

2. Sizing the Distance Array

The nodes are labeled 0 to n - 1, so the distance array needs exactly n entries:

distances = [0] + [float('inf')] * (n - 1)

Writing [0] + [float('inf')] * n creates n + 1 entries. Here that extra entry stays at infinity and is never counted, so the answer is unchanged, but the array no longer matches the node labels. Using a dictionary or an array that is too short (for example, sized by the number of edges) would cause wrong counts or an IndexError.

3. Edge Weight Confusion

A common conceptual mistake is confusing the number of intermediate nodes with the edge weight:

If an edge has cnt intermediate nodes, the total distance to traverse it is cnt + 1
Many incorrectly use cnt as the edge weight directly

Correct approach:

# Each edge with 'cnt' intermediate nodes has weight cnt + 1
graph[start_node].append((end_node, intermediate_count + 1))

Complete Solution with the Stale-Entry Check:

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        from collections import defaultdict
        from heapq import heappush, heappop
      
        # Build adjacency list
        graph = defaultdict(list)
        for u, v, cnt in edges:
            graph[u].append((v, cnt + 1))
            graph[v].append((u, cnt + 1))
      
        # Dijkstra's algorithm
        pq = [(0, 0)]  # (distance, node)
        dist = [float('inf')] * n
        dist[0] = 0
      
        while pq:
            d, u = heappop(pq)
          
            # Skip if we've already processed this node with a better distance
            if d > dist[u]:
                continue
          
            for v, weight in graph[u]:
                new_dist = d + weight
                if new_dist < dist[v]:
                    dist[v] = new_dist
                    heappush(pq, (new_dist, v))
      
        # Count reachable original nodes
        result = sum(d <= maxMoves for d in dist)
      
        # Count reachable intermediate nodes
        for u, v, cnt in edges:
            # Nodes reachable from u side
            from_u = min(cnt, max(0, maxMoves - dist[u]))
            # Nodes reachable from v side  
            from_v = min(cnt, max(0, maxMoves - dist[v]))
            # Total intermediate nodes reachable on this edge
            result += min(cnt, from_u + from_v)
      
        return result

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Depth-First Search

Breadth-First Search

Binary Search

Priority Queue

I don't know