Reachable Nodes In Subdivided Graph

Hard

#0836Time: O(N' + E'), where N' and E' are the number of nodes and edges in the full subdivided graph. This can be up to O(10^8) in the worst case, which is too slow and will result in a 'Time Limit Exceeded' error.Space: O(N' + E'), where N' is the number of nodes and E' is the number of edges in the subdivided graph. In the worst case, `N' = n + sum(cnt_i)` and `E' = sum(cnt_i + 1)`, which can be up to O(10^8), leading to a 'Memory Limit Exceeded' error.1 company

Algorithms

Shortest Path

Data structures

Heap (Priority Queue)Graph

Companies

PhonePe

Prompt

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] = [u_i, v_i, cnt_i] indicates that there is an edge between nodes u_i and v_i in the original graph, and cnt_i is the total number of new nodes that you will subdivide the edge into. Note that cnt_i == 0 means you will not subdivide the edge.

To subdivide the edge [u_i, v_i], replace it with (cnt_i + 1) new edges and cnt_i new nodes. The new nodes are x₁, x₂, ..., x_{cnt_i}, and the new edges are [u_i, x₁], [x₁, x₂], [x₂, x₃], ..., [x_{cnt_i-1}, x_{cnt_i}], [x_{cnt_i}, v_i].

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, 10⁴)
edges[i].length == 3
0 <= u_i < v_i < n
There are no multiple edges in the graph.
0 <= cnt_i <= 10⁴
0 <= maxMoves <= 10⁹
1 <= n <= 3000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves constructing the entire subdivided graph explicitly in memory. After the full graph is built, we can run a standard Breadth-First Search (BFS) starting from node 0 to find all nodes reachable within maxMoves. Since all new edges in the subdivided graph have a length of 1, BFS is a suitable algorithm for finding the shortest paths.

Algorithm

Graph Construction:
1. Initialize an adjacency list for the new, large graph.
2. Create a counter for new node IDs, starting from n.
3. Iterate through each edge [u, v, cnt] from the input edges.
4. For each edge, create cnt new nodes. Connect u to the first new node, chain the new nodes together, and connect the last new node to v. Each of these new connections is an edge of weight 1.
5. Add these new edges to the adjacency list, making sure they are undirected.
Breadth-First Search (BFS):
1. After the full graph is built, initialize a queue for BFS and a dist map to store the shortest distance from node 0 to any other node.
2. Add node 0 to the queue and set its distance to 0 in the dist map: dist[0] = 0.
3. While the queue is not empty, dequeue a node u.
4. Let d be the distance to u. If d is already equal to maxMoves, we cannot explore its neighbors, so continue.
5. For each neighbor v of u, if v has not been visited (i.e., not in dist map), add it to the dist map with distance d + 1 and enqueue v.
Count Nodes:
1. The BFS process populates the dist map with all nodes reachable from node 0 within maxMoves.
2. The total number of reachable nodes is simply the final size of the dist map.

Walkthrough

The core idea is to translate the problem description directly into a data structure. We create a new graph that includes all original nodes and all new subdivided nodes. This approach is straightforward but highly inefficient due to the potential size of the new graph.

1// NOTE: This approach is conceptually correct but will fail due to Time Limit Exceeded (TLE)2// and Memory Limit Exceeded (MLE) on larger test cases.3class Solution {4    public int reachableNodes(int[][] edges, int maxMoves, int n) {5        // 1. Build the explicit subdivided graph6        Map<Integer, List<Integer>> adj = new HashMap<>();7        int currentNodeId = n;8        for (int[] edge : edges) {9            int u = edge[0], v = edge[1], cnt = edge[2];10            int prev = u;11            for (int i = 0; i < cnt; i++) {12                adj.computeIfAbsent(prev, k -> new ArrayList<>()).add(currentNodeId);13                adj.computeIfAbsent(currentNodeId, k -> new ArrayList<>()).add(prev);14                prev = currentNodeId;15                currentNodeId++;16            }17            adj.computeIfAbsent(prev, k -> new ArrayList<>()).add(v);18            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(prev);19        }20 21        // 2. Run BFS to find all reachable nodes22        Queue<Integer> queue = new LinkedList<>();23        Map<Integer, Integer> dist = new HashMap<>();24 25        queue.offer(0);26        dist.put(0, 0);27 28        while (!queue.isEmpty()) {29            int u = queue.poll();30            int d = dist.get(u);31 32            if (d >= maxMoves) {33                continue;34            }35 36            if (adj.containsKey(u)) {37                for (int v : adj.get(u)) {38                    if (!dist.containsKey(v)) {39                        dist.put(v, d + 1);40                        queue.offer(v);41                    }42                }43            }44        }45 46        // 3. The number of reachable nodes is the number of nodes we found a path to.47        return dist.size();48    }49}

Complexity

Time

O(N' + E'), where N' and E' are the number of nodes and edges in the full subdivided graph. This can be up to O(10^8) in the worst case, which is too slow and will result in a 'Time Limit Exceeded' error.

Space

O(N' + E'), where N' is the number of nodes and E' is the number of edges in the subdivided graph. In the worst case, `N' = n + sum(cnt_i)` and `E' = sum(cnt_i + 1)`, which can be up to O(10^8), leading to a 'Memory Limit Exceeded' error.

Trade-offs

Pros

Simple to understand and implement.
Directly models the problem statement without complex logic.

Cons

Extremely high memory usage. The number of nodes and edges in the subdivided graph can be up to O(10^8), which will exceed typical memory limits.
Very slow. The time complexity is proportional to the size of the subdivided graph, which is too large for the given constraints, leading to a 'Time Limit Exceeded' error.

This approach avoids building the large subdivided graph. Instead, it recognizes that the problem can be solved by first finding the shortest paths from node 0 to all other original nodes. The subdivided edges are treated as having a weight equal to the number of new nodes plus one. After finding these shortest paths using Dijkstra's algorithm, we can calculate how many subdivided nodes on each edge are reachable.

Algorithm

Graph Representation:
1. Construct an adjacency list for the original graph. The nodes are 0 to n-1.
2. For each edge [u, v, cnt] in the input, treat it as a weighted edge where the weight is cnt + 1. This weight represents the distance between u and v in the subdivided graph.
Dijkstra's Algorithm:
1. Run Dijkstra's algorithm starting from source node 0 on this weighted graph.
2. Use a priority queue to efficiently find the node with the smallest distance to visit next.
3. Maintain a dist array to store the shortest distance from node 0 to every other original node i.
Calculate Reachable Nodes:
1. Initialize a counter totalReachableNodes to 0.
2. Count original nodes: Iterate through all original nodes i from 0 to n-1. If dist[i] <= maxMoves, it means node i is reachable, so increment the counter.
3. Count subdivided nodes: Iterate through each original edge [u, v, cnt].
  - Calculate the number of moves remaining after reaching u: movesFromU = max(0, maxMoves - dist[u]).
  - Calculate the number of moves remaining after reaching v: movesFromV = max(0, maxMoves - dist[v]).
  - The number of subdivided nodes on this edge that can be reached from either end is movesFromU + movesFromV.
  - This value cannot exceed the total number of subdivided nodes on the edge, which is cnt. So, the number of reachable subdivided nodes on this edge is min(cnt, movesFromU + movesFromV).
  - Add this number to totalReachableNodes.
Return Result:
1. The final value of totalReachableNodes is the answer.

Walkthrough

The key insight is that we only need to know the shortest distance to the original nodes (0 to n-1) to determine reachability. The subdivided nodes don't provide any shortcuts; they only increase path lengths. By working on the much smaller original graph, we can solve the problem efficiently.

1class Solution {2    public int reachableNodes(int[][] edges, int maxMoves, int n) {3        // 1. Build adjacency list for the original graph with weighted edges4        Map<Integer, List<int[]>> adj = new HashMap<>();5        for (int[] edge : edges) {6            int u = edge[0], v = edge[1], cnt = edge[2];7            adj.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{v, cnt + 1});8            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(new int[]{u, cnt + 1});9        }10 11        // 2. Run Dijkstra's algorithm from node 012        int[] dist = new int[n];13        Arrays.fill(dist, Integer.MAX_VALUE);14        dist[0] = 0;15 16        // PriorityQueue stores {distance, node}17        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));18        pq.offer(new int[]{0, 0});19 20        while (!pq.isEmpty()) {21            int[] curr = pq.poll();22            int d = curr[0];23            int u = curr[1];24 25            if (d > dist[u]) {26                continue;27            }28 29            if (adj.containsKey(u)) {30                for (int[] neighbor : adj.get(u)) {31                    int v = neighbor[0];32                    int weight = neighbor[1];33                    if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {34                        dist[v] = dist[u] + weight;35                        pq.offer(new int[]{dist[v], v});36                    }37                }38            }39        }40 41        // 3. Calculate total reachable nodes42        int totalReachableNodes = 0;43 44        // Count reachable original nodes45        for (int i = 0; i < n; i++) {46            if (dist[i] <= maxMoves) {47                totalReachableNodes++;48            }49        }50 51        // Count reachable subdivided nodes52        for (int[] edge : edges) {53            int u = edge[0], v = edge[1], cnt = edge[2];54            55            long movesFromU = (dist[u] == Integer.MAX_VALUE) ? 0 : maxMoves - dist[u];56            long movesFromV = (dist[v] == Integer.MAX_VALUE) ? 0 : maxMoves - dist[v];57            58            long reachableOnEdge = Math.max(0, movesFromU) + Math.max(0, movesFromV);59            60            totalReachableNodes += Math.min(cnt, reachableOnEdge);61        }62 63        return totalReachableNodes;64    }65}

Complexity

Time

O(E log N), where E is the number of original edges and N is the number of original nodes. This is dominated by Dijkstra's algorithm with a priority queue. Given the constraints, this is very efficient.

Space

O(N + E), where N is the number of original nodes and E is the number of original edges. This is for storing the adjacency list, the distance array, and the priority queue, which is well within memory limits.

Trade-offs

Pros

Highly efficient in both time and space.
Avoids the creation of the massive subdivided graph, working only with the original graph's dimensions.
Correctly handles all cases within the given constraints.

Cons

The logic is more complex than the brute-force approach, requiring understanding of Dijkstra's algorithm and insights into how to count the subdivided nodes without creating them.

Solutions

Solution

1class Solution {2public3  int reachableNodes(int[][] edges, int maxMoves, int n) {4    List<int[]>[] g = new List[n];5    Arrays.setAll(g, e->new ArrayList<>());6    for (var e : edges) {7      int u = e[0], v = e[1], cnt = e[2] + 1;8      g[u].add(new int[]{v, cnt});9      g[v].add(new int[]{u, cnt});10    }11    int[] dist = new int[n];12    Arrays.fill(dist, 1 << 30);13    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] - b[0]);14    q.offer(new int[]{0, 0});15    dist[0] = 0;16    while (!q.isEmpty()) {17      var p = q.poll();18      int d = p[0], u = p[1];19      for (var nxt : g[u]) {20        int v = nxt[0], cnt = nxt[1];21        if (d + cnt < dist[v]) {22          dist[v] = d + cnt;23          q.offer(new int[]{dist[v], v});24        }25      }26    }27    int ans = 0;28    for (int d : dist) {29      if (d <= maxMoves) {30        ++ans;31      }32    }33    for (var e : edges) {34      int u = e[0], v = e[1], cnt = e[2];35      int a = Math.min(cnt, Math.max(0, maxMoves - dist[u]));36      int b = Math.min(cnt, Math.max(0, maxMoves - dist[v]));37      ans += Math.min(cnt, a + b);38    }39    return ans;40  }41}

1class Solution {2public:3  int reachableNodes(vector<vector<int>> &edges, int maxMoves, int n) {4    using pii = pair<int, int>;5    vector<vector<pii>> g(n);6    for (auto &e : edges) {7      int u = e[0], v = e[1], cnt = e[2] + 1;8      g[u].emplace_back(v, cnt);9      g[v].emplace_back(u, cnt);10    }11    priority_queue<pii, vector<pii>, greater<pii>> q;12    q.emplace(0, 0);13    int dist[n];14    memset(dist, 0x3f, sizeof dist);15    dist[0] = 0;16    while (!q.empty()) {17      auto [d, u] = q.top();18      q.pop();19      for (auto &[v, cnt] : g[u]) {20        if (d + cnt < dist[v]) {21          dist[v] = d + cnt;22          q.emplace(dist[v], v);23        }24      }25    }26    int ans = 0;27    for (int &d : dist)28      ans += d <= maxMoves;29    for (auto &e : edges) {30      int u = e[0], v = e[1], cnt = e[2];31      int a = min(cnt, max(0, maxMoves - dist[u]));32      int b = min(cnt, max(0, maxMoves - dist[v]));33      ans += min(cnt, a + b);34    }35    return ans;36  }37};

1class Solution:2    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int: g = defaultdict(list) for u, v, cnt in edges: g[u]. append((v, cnt + 1)) g[v]. append((u, cnt + 1)) q = [(0, 0)] dist = [0] + [inf] * n while q: d, u = heappop(q) for v, cnt in g[u]: if (t: = d + cnt) < dist[v]: dist[v] = t q . append((t, v)) ans = sum(d <= maxMoves for d in dist) 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) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem