Reachable Nodes In Subdivided Graph — Problem & Solution
Reachable Nodes In Subdivided Graph solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Reachable Nodes In Subdivided Graph is a hard coding problem on graph, heap and shortest path, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Graph, Heap, Shortest Path
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an undirected graph with n nodes labelled 0 to n - 1. Each edges[i] = [u, v, cnt] means the edge between u and v is subdivided into a chain of cnt + 1 edges by inserting cnt new nodes x1, …, xcnt between them: [u, x1], [x1, x2], …, [xcnt, v]. With cnt == 0 the edge is left as it is.
In the new graph you start at node 0 and may walk at most maxMoves edges. Return how many nodes of the new graph (original and inserted) are reachable from node 0.
Example 1
Input: edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
Output: 13
Explanation: Node 2 is 2 moves away and node 1 is 5 moves away (0 → 2 → 1 through three new nodes); counting the inserted nodes each side can still reach gives 13.
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 has no edges, so only node 0 itself is reachable.
Constraints
0 <= edges.length <= min(n * (n - 1) / 2, 10^4)edges[i].length == 30 <= u < v < nthere are no multiple edges0 <= cnt <= 10^40 <= maxMoves <= 10^91 <= n <= 3000
Hints for Reachable Nodes In Subdivided Graph
Hint 1
Never build the subdivided graph — a single edge can hide ten thousand nodes. Treat edge
[u, v, cnt]as a weighted edge of lengthcnt + 1.Hint 2
Shortest distances from
0to the original nodes come from Dijkstra. An original node counts when its distance is at mostmaxMoves.Hint 3
For the inserted nodes on edge
(u, v): fromuyou can walkmax(0, maxMoves - dist[u])of them, fromvmax(0, maxMoves - dist[v]). The edge contributes the sum of those, capped atcnt.
How to solve Reachable Nodes In Subdivided Graph
Count original nodes and inserted nodes separately. Original nodes need true shortest distances (Dijkstra with weights cnt + 1); inserted nodes on an edge are reached by walking in from either end with whatever moves remain.
Approach
- Build an adjacency list where edge
[u, v, cnt]has weightcnt + 1in both directions. - Run Dijkstra from node
0to getdist[x]for every original node (infinity if unreachable). - Count original nodes with
dist[x] <= maxMoves. - For each edge, let
a = min(cnt, max(0, maxMoves - dist[u]))andb = min(cnt, max(0, maxMoves - dist[v])); addmin(cnt, a + b). - Return the total.
Why it works
Any walk reaching an inserted node on edge (u, v) enters the chain through u or v, so the best it can do from u is walk the leftover budget maxMoves - dist[u] along the chain, and likewise from v. The nodes reached from both ends overlap only when the two stretches meet, which the cap at cnt handles. Original nodes are reachable exactly when their shortest distance fits in the budget.
Complexity
- Time —
O(n^2 + E) with an array-based Dijkstra (or O(E log n) with a heap) - Space —
O(n + E)
Pitfalls
- Inserted nodes are counted per edge, never through
dist— they are not vertices of the Dijkstra graph. a + bmay count the middle twice; cap the edge's contribution atcnt.maxMovescan be10^9: compute the leftover budgets before adding them, or use 64-bit arithmetic.
Reference solution
Python
import heapq
from typing import List
def reachableNodes(edges: List[List[int]], maxMoves: int, n: int) -> int:
adj = [[] for _ in range(n)]
for u, v, cnt in edges:
adj[u].append((v, cnt + 1))
adj[v].append((u, cnt + 1))
INF = float('inf')
dist = [INF] * n
dist[0] = 0
heap = [(0, 0)]
while heap:
d, x = heapq.heappop(heap)
if d > dist[x]:
continue
for y, w in adj[x]:
if d + w < dist[y]:
dist[y] = d + w
heapq.heappush(heap, (d + w, y))
total = sum(1 for x in range(n) if dist[x] <= maxMoves)
for u, v, cnt in edges:
a = min(cnt, max(0, maxMoves - dist[u])) if dist[u] != INF else 0
b = min(cnt, max(0, maxMoves - dist[v])) if dist[v] != INF else 0
total += min(cnt, a + b)
return totalJava
public static int reachableNodes(int[][] edges, int maxMoves, int n) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2] + 1}); adj.get(e[1]).add(new int[]{e[0], e[2] + 1}); }
final int INF = Integer.MAX_VALUE;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
pq.add(new int[]{0, 0});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], x = top[1];
if (d > dist[x]) continue;
for (int[] nb : adj.get(x)) {
if (d + nb[1] < dist[nb[0]]) { dist[nb[0]] = d + nb[1]; pq.add(new int[]{dist[nb[0]], nb[0]}); }
}
}
int total = 0;
for (int x = 0; x < n; x++) if (dist[x] <= maxMoves) total++;
for (int[] e : edges) {
int a = dist[e[0]] == INF ? 0 : Math.min(e[2], Math.max(0, maxMoves - dist[e[0]]));
int b = dist[e[1]] == INF ? 0 : Math.min(e[2], Math.max(0, maxMoves - dist[e[1]]));
total += Math.min(e[2], a + b);
}
return total;
}C++
int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
vector<vector<pair<int, int>>> adj(n);
for (auto& e : edges) { adj[e[0]].push_back({e[1], e[2] + 1}); adj[e[1]].push_back({e[0], e[2] + 1}); }
const int INF = INT_MAX;
vector<int> dist(n, INF);
dist[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
while (!pq.empty()) {
int d = pq.top().first, x = pq.top().second;
pq.pop();
if (d > dist[x]) continue;
for (auto& e : adj[x]) {
int y = e.first, w = e.second;
if (d + w < dist[y]) { dist[y] = d + w; pq.push({dist[y], y}); }
}
}
int total = 0;
for (int x = 0; x < n; x++) if (dist[x] <= maxMoves) total++;
for (auto& e : edges) {
int a = dist[e[0]] == INF ? 0 : min(e[2], max(0, maxMoves - dist[e[0]]));
int b = dist[e[1]] == INF ? 0 : min(e[2], max(0, maxMoves - dist[e[1]]));
total += min(e[2], a + b);
}
return total;
}JavaScript
var reachableNodes = function(edges, maxMoves, n) {
var adj = [], dist = [], done = [], INF = 2000000000;
for (var i = 0; i < n; i++) { adj.push([]); dist.push(INF); done.push(false); }
for (var k = 0; k < edges.length; k++) {
var e = edges[k];
adj[e[0]].push([e[1], e[2] + 1]);
adj[e[1]].push([e[0], e[2] + 1]);
}
dist[0] = 0;
// Array-based Dijkstra: n is at most 3000, so O(n^2) is fine.
for (var it = 0; it < n; it++) {
var x = -1;
for (var j = 0; j < n; j++) if (!done[j] && dist[j] < INF && (x === -1 || dist[j] < dist[x])) x = j;
if (x === -1) break;
done[x] = true;
for (var a = 0; a < adj[x].length; a++) {
var y = adj[x][a][0], w = adj[x][a][1];
if (dist[x] + w < dist[y]) dist[y] = dist[x] + w;
}
}
var total = 0;
for (var z = 0; z < n; z++) if (dist[z] <= maxMoves) total++;
for (var q = 0; q < edges.length; q++) {
var u = edges[q][0], v = edges[q][1], cnt = edges[q][2];
var left = Math.min(cnt, Math.max(0, maxMoves - dist[u]));
var right = Math.min(cnt, Math.max(0, maxMoves - dist[v]));
total += Math.min(cnt, left + right);
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 107 graph problems · the whole catalogue
Learn the technique: Graph Data Structure · Heaps and Priority Queues