LeetCode 882: Reachable Nodes In Subdivided Graph Solution

Master LeetCode problem 882 (Reachable Nodes In Subdivided Graph), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

882. Reachable Nodes In Subdivided Graph

Hard

Graph Heap (Priority Queue)Shortest Path

Problem Explanation

Explanation

To solve this problem, we can use Dijkstra's algorithm to find the shortest distances from node 0 to all other nodes in the graph. Then, we can iterate through each edge and calculate how many nodes are reachable based on the number of subdivisions and the distances between nodes.

Initialize a distance array to store the shortest distance from node 0 to all other nodes. Initialize it with a maximum value except for node 0 where distance is 0.
Implement Dijkstra's algorithm to find the shortest distances from node 0 to all other nodes.
Iterate through each edge in the original graph and calculate the number of reachable nodes based on the subdivisions and distances.
Keep track of the total reachable nodes and return the count.

Time Complexity: O(n^2 log n) where n is the number of nodes
Space Complexity: O(n^2)

Solution Code

class Solution {
    public int reachableNodes(int[][] edges, int maxMoves, int n) {
        Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            graph.computeIfAbsent(u, k -> new HashMap<>()).put(v, cnt);
            graph.computeIfAbsent(v, k -> new HashMap<>()).put(u, cnt);
        }
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0}); // distance, node
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0], node = curr[1];
            if (d > dist[node]) continue;
            
            for (int neighbor : graph.getOrDefault(node, new HashMap<>()).keySet()) {
                int cnt = graph.get(node).get(neighbor);
                int newDist = d + cnt + 1;
                if (newDist < dist[neighbor]) {
                    dist[neighbor] = newDist;
                    pq.offer(new int[]{newDist, neighbor});
                }
            }
        }
        
        int ans = 0;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], cnt = edge[2];
            int reachable = Math.min(cnt, Math.max(0, maxMoves - dist[u])) + Math.min(cnt, Math.max(0, maxMoves - dist[v]));
            ans += Math.min(reachable, cnt);
        }
        
        for (int d : dist) {
            if (d <= maxMoves) ans++;
        }
        
        return ans;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 882 (Reachable Nodes In Subdivided Graph)?

This page provides optimized solutions for LeetCode problem 882 (Reachable Nodes In Subdivided Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 882 (Reachable Nodes In Subdivided Graph)?

The time complexity for LeetCode 882 (Reachable Nodes In Subdivided Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 882 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 882 in Java, C++, or Python.

Back to LeetCode Solutions