Reachable Nodes In Subdivided Graph

Hard
1688.

Reachable Nodes In Subdivided Graph

HardGraphHeap (Priority Queue)Shortest PathGoogleAmazon

Reachable Nodes In Subdivided Graph is a hard coding problem on graph, heap and shortest path, asked in Amazon and Google interviews.

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 == 3
  • 0 <= u < v < n
  • there are no multiple edges
  • 0 <= cnt <= 10^4
  • 0 <= maxMoves <= 10^9
  • 1 <= n <= 3000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} edges
 * @param {number} maxMoves
 * @param {number} n
 * @return {number}
 */
var reachableNodes = function(edges, maxMoves, n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 == 3
  • 0 <= u < v < n
  • there are no multiple edges
  • 0 <= cnt <= 10^4
  • 0 <= maxMoves <= 10^9
  • 1 <= n <= 3000

Hints for Reachable Nodes In Subdivided Graph

  1. 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 length cnt + 1.

  2. Hint 2

    Shortest distances from 0 to the original nodes come from Dijkstra. An original node counts when its distance is at most maxMoves.

  3. Hint 3

    For the inserted nodes on edge (u, v): from u you can walk max(0, maxMoves - dist[u]) of them, from v max(0, maxMoves - dist[v]). The edge contributes the sum of those, capped at cnt.

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

  1. Build an adjacency list where edge [u, v, cnt] has weight cnt + 1 in both directions.
  2. Run Dijkstra from node 0 to get dist[x] for every original node (infinity if unreachable).
  3. Count original nodes with dist[x] <= maxMoves.
  4. For each edge, let a = min(cnt, max(0, maxMoves - dist[u])) and b = min(cnt, max(0, maxMoves - dist[v])); add min(cnt, a + b).
  5. 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 + b may count the middle twice; cap the edge's contribution at cnt.
  • maxMoves can be 10^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 total

Java

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