Reachable Nodes in Subdivided Graph — Dijkstra plus Edge-Subdivision Counting

Problem Statement#

You are given an undirected graph with n nodes and a list of edges where each edge is [u, v, cnt], meaning the edge from u to v has cnt new intermediate nodes inserted along it (subdividing the edge into cnt + 1 smaller pieces). Starting from node 0 with a budget of maxMoves moves, count the total number of distinct nodes (original or subdivided) you can reach.

You can move only along the subdivided edges, each move costs one unit, and once your budget hits zero you cannot continue.

Why This Problem Matters#

Reachable Nodes in Subdivided Graph is a senior-level Dijkstra problem asked at Google, Amazon, and Snowflake interviews. It tests whether you can compute shortest paths on the original (non-subdivided) graph and then translate distances into edge-subdivision counts. Naively expanding every subdivided node into the graph blows up memory because cnt can be very large per edge; the trick is to keep the original graph and account for the subdivisions analytically.

The problem rewards two skills: choosing Dijkstra on a small original graph instead of BFS on the giant expanded graph, and deriving the per-edge subdivision count from remaining-move information at the two endpoints. This is the kind of question that filters senior engineers from juniors who reach for BFS first.

The Core Insight#

Run Dijkstra from node 0 on the original graph where each edge from u to v with cnt subdivisions effectively has length cnt + 1 (you traverse cnt + 1 units to cross). Track dist[v] as the maximum remaining moves when you reach v. Equivalently, store rem[v] = maxMoves - shortestDistance[v] so that rem[v] directly tells you how many more moves you have left after arriving at v.

For counting:

1. Every original node v with rem[v] >= 0 is reachable; add the count of such nodes to the answer.
2. For each edge (u, v, cnt), you may walk into the edge from u covering min(cnt, rem[u]) subdivision nodes, and from v covering min(cnt, rem[v]) subdivision nodes. The total subdivision nodes reachable on that edge equals the lesser of cnt and the sum from both sides because the same subdivision node should not be double-counted.

The maximum-priority-heap (Dijkstra) trick of storing -rem lets you pop the highest remaining moves first.

Visual Dry Run (BFS/DFS trace)#

Take edges [[0, 1, 4], [1, 2, 6], [0, 2, 8], [1, 3, 1]], maxMoves equal to 10, n equal to 4.

Adjacency. Edge weights are cnt + 1. Edge 0-1 has weight 5, edge 1-2 has weight 7, edge 0-2 has weight 9, edge 1-3 has weight 2.

Dijkstra from 0 storing remaining moves. Init rem array equals [-1, -1, -1, -1]. Push (-10, 0) onto the max-heap (we negate to use Python's min-heap as a max-heap). Set rem[0] to 10.

Pop (-10, 0). d equals 10 equals rem[0]. For neighbor 1 with weight 5, candidate remaining is 10 - 5 = 5. 5 greater than rem[1] of -1, so set rem[1] to 5 and push (-5, 1). For neighbor 2 with weight 9, candidate is 1. Set rem[2] to 1 and push (-1, 2).

Pop (-5, 1). d equals 5 equals rem[1]. Neighbor 0 candidate is 0; 0 not greater than rem[0] of 10, skip. Neighbor 2 candidate is 5 - 7 = -2, negative, skip. Neighbor 3 candidate is 5 - 2 = 3. Set rem[3] to 3 and push (-3, 3).

Pop (-3, 3). Neighbor 1 candidate is 1; 1 not greater than rem[1] of 5, skip.

Pop (-1, 2). Neighbor 0 candidate is 1 - 9 = -8, skip. Neighbor 1 candidate is 1 - 7 = -6, skip.

Heap empty. rem equals [10, 5, 1, 3]. All four original nodes reachable, contributing 4.

Per-edge subdivision counting. Edge (0, 1, 4): from 0 walk in min(4, 10) = 4, from 1 walk in min(4, 5) = 4. Sum is 8 but capped at cnt of 4. Add 4. Edge (1, 2, 6): from 1 walk min(6, 5) = 5, from 2 walk min(6, 1) = 1. Sum 6 capped at 6. Add 6. Edge (0, 2, 8): from 0 walk min(8, 10) = 8, from 2 walk min(8, 1) = 1. Sum 9 capped at 8. Add 8. Edge (1, 3, 1): from 1 walk min(1, 5) = 1, from 3 walk min(1, 3) = 1. Sum 2 capped at 1. Add 1.

Total subdivisions counted: 4 plus 6 plus 8 plus 1 equals 19. Plus 4 original nodes equals 23. The LeetCode expected answer is 23.

Solution (Optimal)#

Python — Dijkstra with edge-subdivision counting#

import heapq
from collections import defaultdict
 
class Solution:
    def reachableNodes(self, edges, maxMoves, n):
        adj = defaultdict(dict)
        for u, v, cnt in edges:
            adj[u][v] = cnt
            adj[v][u] = cnt
        rem = [-1] * n
        rem[0] = maxMoves
        heap = [(-maxMoves, 0)]
        while heap:
            d, u = heapq.heappop(heap)
            d = -d
            if d < rem[u]:
                continue
            for v, cnt in adj[u].items():
                nd = d - cnt - 1
                if nd >= 0 and nd > rem[v]:
                    rem[v] = nd
                    heapq.heappush(heap, (-nd, v))
        ans = sum(1 for r in rem if r >= 0)
        for u, v, cnt in edges:
            a = rem[u] if rem[u] >= 0 else 0
            b = rem[v] if rem[v] >= 0 else 0
            ans += min(cnt, a + b)
        return ans

JavaScript#

var reachableNodes = function(edges, maxMoves, n) {
    const adj = Array.from({ length: n }, () => new Map());
    for (const [u, v, cnt] of edges) {
        adj[u].set(v, cnt);
        adj[v].set(u, cnt);
    }
    const rem = new Array(n).fill(-1);
    rem[0] = maxMoves;
    const heap = [[-maxMoves, 0]];
    const cmp = (a, b) => a[0] - b[0];
    while (heap.length) {
        heap.sort(cmp);
        const [negD, u] = heap.shift();
        const d = -negD;
        if (d < rem[u]) continue;
        for (const [v, cnt] of adj[u]) {
            const nd = d - cnt - 1;
            if (nd >= 0 && nd > rem[v]) {
                rem[v] = nd;
                heap.push([-nd, v]);
            }
        }
    }
    let ans = rem.filter(r => r >= 0).length;
    for (const [u, v, cnt] of edges) {
        const a = rem[u] >= 0 ? rem[u] : 0;
        const b = rem[v] >= 0 ? rem[v] : 0;
        ans += Math.min(cnt, a + b);
    }
    return ans;
};

Time complexity is O(E log V) for Dijkstra plus O(E) for the per-edge counting. Space is O(V plus E).

Common Mistakes#

Building the expanded graph with all subdivision nodes blows the memory budget; never do that. Forgetting to add 1 for the destination node in edge weight (the edge has cnt + 1 segments, not cnt) gives off-by-one errors. Counting double when subdivisions from both endpoints overlap gives an overestimate; always cap the sum at cnt. Treating unreachable endpoints as having rem equal to 0 instead of negative pollutes the count; map any negative rem to 0 explicitly. Initializing the heap with (0, 0) instead of (maxMoves, 0) confuses the meaning of rem; pick one convention (remaining moves or distance from source) and stick with it.

Interview Tips#

Lead with the choice of state: keep the original graph and store remaining moves at each node. Explain why Dijkstra rather than BFS: edge weights are unit length per move, but each original edge has cnt + 1 units, so the search must compare distances. Walk through the per-edge subdivision counting carefully; this is where most candidates stumble. Mention the cap at cnt to avoid double counting. Discuss the heap-based max approach via negation. If asked, describe how Bellman-Ford could substitute on graphs with negative weights (not relevant here but a good signal of breadth).

Follow-up Questions#

What if some edges are directed? Build the adjacency with directional weights and run Dijkstra on the directed graph; counting per-edge subdivisions only allows the source side to extend into the edge. What if the budget is so large that every node is reachable? The answer simplifies to n original nodes plus the sum of all cnt values. How do you reconstruct one path that reaches the most subdivision nodes? Use parent pointers during Dijkstra and reconstruct at the end. What if you need the specific subdivision nodes touched, not just the count? Reconstruct each edge's contribution and emit synthetic identifiers.

Key Takeaways#

• Never expand subdivision nodes; run Dijkstra on the original graph
• Track remaining moves at each original node; that drives both reach and edge-segment counting
• Each edge contributes min(cnt, rem[u] + rem[v]) subdivision nodes, capped to avoid double counting
• Edge weight in Dijkstra equals cnt + 1, not cnt
• Map negative rem to 0 before counting subdivisions to avoid silent bugs
• Pattern is a senior-level Dijkstra plus accounting trick used in mesh routing and partial reachability