Scale Engineer

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

To subdivide the edge [ui, vi], replace it with (cnti + 1) new edges and cnti new nodes. The new nodes are x1, x2, ..., xcnti, and the new edges are [ui, x1], [x1, x2], [x2, x3], ..., [xcnti-1, xcnti], [xcnti, vi].

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, 104)
  • edges[i].length == 3
  • 0 <= ui < vi < n
  • There are no multiple edges in the graph.
  • 0 <= cnti <= 104
  • 0 <= maxMoves <= 109
  • 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.

// NOTE: This approach is conceptually correct but will fail due to Time Limit Exceeded (TLE)// and Memory Limit Exceeded (MLE) on larger test cases.class Solution {    public int reachableNodes(int[][] edges, int maxMoves, int n) {        // 1. Build the explicit subdivided graph        Map<Integer, List<Integer>> adj = new HashMap<>();        int currentNodeId = n;        for (int[] edge : edges) {            int u = edge[0], v = edge[1], cnt = edge[2];            int prev = u;            for (int i = 0; i < cnt; i++) {                adj.computeIfAbsent(prev, k -> new ArrayList<>()).add(currentNodeId);                adj.computeIfAbsent(currentNodeId, k -> new ArrayList<>()).add(prev);                prev = currentNodeId;                currentNodeId++;            }            adj.computeIfAbsent(prev, k -> new ArrayList<>()).add(v);            adj.computeIfAbsent(v, k -> new ArrayList<>()).add(prev);        }         // 2. Run BFS to find all reachable nodes        Queue<Integer> queue = new LinkedList<>();        Map<Integer, Integer> dist = new HashMap<>();         queue.offer(0);        dist.put(0, 0);         while (!queue.isEmpty()) {            int u = queue.poll();            int d = dist.get(u);             if (d >= maxMoves) {                continue;            }             if (adj.containsKey(u)) {                for (int v : adj.get(u)) {                    if (!dist.containsKey(v)) {                        dist.put(v, d + 1);                        queue.offer(v);                    }                }            }        }         // 3. The number of reachable nodes is the number of nodes we found a path to.        return dist.size();    }}

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.

Solutions

class Solution {public  int reachableNodes(int[][] edges, int maxMoves, int n) {    List<int[]>[] g = new List[n];    Arrays.setAll(g, e->new ArrayList<>());    for (var e : edges) {      int u = e[0], v = e[1], cnt = e[2] + 1;      g[u].add(new int[]{v, cnt});      g[v].add(new int[]{u, cnt});    }    int[] dist = new int[n];    Arrays.fill(dist, 1 << 30);    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->a[0] - b[0]);    q.offer(new int[]{0, 0});    dist[0] = 0;    while (!q.isEmpty()) {      var p = q.poll();      int d = p[0], u = p[1];      for (var nxt : g[u]) {        int v = nxt[0], cnt = nxt[1];        if (d + cnt < dist[v]) {          dist[v] = d + cnt;          q.offer(new int[]{dist[v], v});        }      }    }    int ans = 0;    for (int d : dist) {      if (d <= maxMoves) {        ++ans;      }    }    for (var e : edges) {      int u = e[0], v = e[1], cnt = e[2];      int a = Math.min(cnt, Math.max(0, maxMoves - dist[u]));      int b = Math.min(cnt, Math.max(0, maxMoves - dist[v]));      ans += Math.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 →

Next problem