LeetCode 882 - Reachable Nodes In Subdivided Graph

The problem gives us an undirected graph with n original nodes. Each edge has an associated subdivision count, meaning the edge is replaced by a chain of intermediate nodes. For an edge [u, v, cnt], the original direct connection between u and v no longer exists as a single edge.

leetcodehardgraph-theoryheap-(priority-queue)shortest-path

LeetCode Problem 882

Difficulty: 🔴 Hard
Topics: Graph Theory, Heap (Priority Queue), Shortest Path

Solution

Problem Understanding

The problem gives us an undirected graph with n original nodes. Each edge has an associated subdivision count, meaning the edge is replaced by a chain of intermediate nodes.

For an edge [u, v, cnt], the original direct connection between u and v no longer exists as a single edge. Instead, the edge becomes:

u -> x1 -> x2 -> ... -> xcnt -> v

This transformation inserts cnt new nodes between u and v, and the total path length between the original endpoints becomes cnt + 1.

We start from node 0 and can move at most maxMoves steps. The goal is to count how many nodes in the fully subdivided graph are reachable.

An important detail is that the subdivided nodes do not explicitly appear in the input. The graph only stores the original nodes and subdivision counts. A naive implementation that physically constructs every subdivided node could become enormous because:

  • n can be up to 3000
  • edges.length can be up to 10000
  • cnti can be up to 10000

In the worst case, the number of subdivided nodes could reach tens of millions, which is far too large to build directly.

The key observation is that traversing an edge with cnt subdivisions costs cnt + 1 moves from one original node to the other original node. This turns the problem into a shortest path problem on the original graph.

The output must include:

  • All reachable original nodes
  • All reachable subdivided nodes along each edge

The constraints strongly suggest that we need an efficient shortest path algorithm, specifically Dijkstra's algorithm with a priority queue.

Several edge cases are important:

  • Node 0 may be disconnected from the graph
  • maxMoves may be 0
  • Some edges may have cnt = 0
  • A subdivided edge may be partially reachable from one side and partially reachable from the other side
  • We must avoid double counting subdivided nodes when both endpoints can reach into the same edge

Approaches

Brute Force Approach

The brute force solution explicitly constructs the fully subdivided graph.

For every edge [u, v, cnt], we create cnt intermediate nodes and connect them into a chain. After building the expanded graph, we run a standard BFS or Dijkstra traversal from node 0 to count all reachable nodes.

This approach is correct because it directly models the graph described in the problem statement. Every move in the expanded graph corresponds exactly to one move in the problem definition.

However, this approach is infeasible for the given constraints. If every edge contains many subdivisions, the expanded graph becomes enormous. With up to 10000 edges and each edge containing up to 10000 new nodes, the graph could contain tens of millions of nodes and edges.

Both memory usage and runtime become unacceptable.

Optimal Approach

The key insight is that we never actually need to construct the subdivided nodes.

Suppose an edge has cnt subdivided nodes. Moving from one endpoint to the other requires exactly cnt + 1 moves. Therefore, we can treat the original graph as a weighted graph where:

weight(u, v) = cnt + 1

Now we run Dijkstra's algorithm from node 0 to compute the shortest distance to every original node.

Once we know the shortest distances:

  • Every original node with distance <= maxMoves is reachable
  • For each edge, we determine how many subdivided nodes can be reached from each endpoint

If:

remainingFromU = max(0, maxMoves - dist[u])
remainingFromV = max(0, maxMoves - dist[v])

then:

  • We can enter at most remainingFromU subdivided nodes from side u
  • We can enter at most remainingFromV subdivided nodes from side v

But the edge only contains cnt subdivided nodes total, so the reachable subdivided nodes are:

min(cnt, remainingFromU + remainingFromV)

This avoids double counting.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(V' + E') O(V' + E') Explicitly builds the subdivided graph
Optimal O((V + E) log V) O(V + E) Uses Dijkstra on original graph only

Here, V' and E' represent the size of the expanded graph, which can become extremely large.

Algorithm Walkthrough

  1. Build an adjacency list for the original graph.

Each edge [u, v, cnt] becomes:

u -> (v, cnt + 1)
v -> (u, cnt + 1)

We use cnt + 1 because traversing all subdivided nodes plus the final endpoint costs that many moves. 2. Run Dijkstra's algorithm starting from node 0.

We maintain:

  • A min heap storing (distance, node)
  • A distance array initialized to infinity
  • dist[0] = 0

Dijkstra is appropriate because all edge weights are positive. 3. Process nodes in increasing shortest distance order.

For each popped node:

  • If we already found a shorter path, skip it
  • Otherwise, relax all neighboring edges

If:

newDist = currentDist + weight

and newDist < dist[neighbor], update the distance and push the neighbor into the heap. 4. Count reachable original nodes.

Every node with:

dist[node] <= maxMoves

contributes one reachable node. 5. Count reachable subdivided nodes on every edge.

For edge [u, v, cnt]:

reachableFromU = max(0, maxMoves - dist[u])
reachableFromV = max(0, maxMoves - dist[v])

The total reachable subdivided nodes are:

min(cnt, reachableFromU + reachableFromV)

This correctly handles overlap when both sides reach into the same edge. 6. Return the total count.

Why it works

Dijkstra guarantees the shortest path distance from node 0 to every original node because all edge weights are positive.

A subdivided node is reachable if we can enter far enough into its edge from either endpoint. The formula:

min(cnt, reachableFromU + reachableFromV)

counts exactly the number of unique subdivided nodes reachable on that edge. Since every edge is processed independently and original nodes are counted separately, the final answer is correct.

Python Solution

from typing import List
import heapq

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        graph = [[] for _ in range(n)]

        for u, v, cnt in edges:
            weight = cnt + 1
            graph[u].append((v, weight))
            graph[v].append((u, weight))

        INF = float("inf")
        dist = [INF] * n
        dist[0] = 0

        min_heap = [(0, 0)]

        while min_heap:
            current_dist, node = heapq.heappop(min_heap)

            if current_dist > dist[node]:
                continue

            for neighbor, weight in graph[node]:
                new_dist = current_dist + weight

                if new_dist < dist[neighbor]:
                    dist[neighbor] = new_dist
                    heapq.heappush(min_heap, (new_dist, neighbor))

        reachable_count = 0

        # Count reachable original nodes
        for d in dist:
            if d <= maxMoves:
                reachable_count += 1

        # Count reachable subdivided nodes
        for u, v, cnt in edges:
            reachable_from_u = max(0, maxMoves - dist[u])
            reachable_from_v = max(0, maxMoves - dist[v])

            reachable_count += min(
                cnt,
                reachable_from_u + reachable_from_v
            )

        return reachable_count

The implementation begins by constructing an adjacency list where each edge weight is cnt + 1. This models the traversal cost through all subdivided nodes between the two original endpoints.

The dist array stores the shortest known distance from node 0 to every original node. Dijkstra's algorithm processes nodes in increasing distance order using a min heap.

The stale entry check:

if current_dist > dist[node]:
    continue

prevents unnecessary processing when a better path has already been discovered.

After shortest paths are computed, the algorithm counts all original nodes reachable within maxMoves.

The second pass over the edges computes how many subdivided nodes are reachable on each edge. Since movement can occur from both endpoints, the algorithm adds the reachable portions together but caps the result at cnt to avoid double counting.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type Pair struct {
	node int
	dist int
}

type MinHeap []Pair

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].dist < h[j].dist
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Pair))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func reachableNodes(edges [][]int, maxMoves int, n int) int {
	graph := make([][][2]int, n)

	for _, edge := range edges {
		u, v, cnt := edge[0], edge[1], edge[2]
		weight := cnt + 1

		graph[u] = append(graph[u], [2]int{v, weight})
		graph[v] = append(graph[v], [2]int{u, weight})
	}

	dist := make([]int, n)

	for i := 0; i < n; i++ {
		dist[i] = math.MaxInt
	}

	dist[0] = 0

	minHeap := &MinHeap{}
	heap.Init(minHeap)
	heap.Push(minHeap, Pair{node: 0, dist: 0})

	for minHeap.Len() > 0 {
		current := heap.Pop(minHeap).(Pair)

		if current.dist > dist[current.node] {
			continue
		}

		for _, neighbor := range graph[current.node] {
			nextNode := neighbor[0]
			weight := neighbor[1]

			newDist := current.dist + weight

			if newDist < dist[nextNode] {
				dist[nextNode] = newDist
				heap.Push(minHeap, Pair{
					node: nextNode,
					dist: newDist,
				})
			}
		}
	}

	reachableCount := 0

	for _, d := range dist {
		if d <= maxMoves {
			reachableCount++
		}
	}

	for _, edge := range edges {
		u, v, cnt := edge[0], edge[1], edge[2]

		reachableFromU := 0
		reachableFromV := 0

		if dist[u] <= maxMoves {
			reachableFromU = maxMoves - dist[u]
		}

		if dist[v] <= maxMoves {
			reachableFromV = maxMoves - dist[v]
		}

		reachableCount += min(
			cnt,
			reachableFromU+reachableFromV,
		)
	}

	return reachableCount
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same logic as the Python version but requires an explicit heap implementation using the container/heap package.

The adjacency list uses slices of fixed-size arrays:

[][2]int

where each entry stores:

[neighbor, weight]

Go does not provide built in infinity values for integers, so the implementation initializes distances with math.MaxInt.

The heap stores custom Pair structs containing the node and its current shortest distance.

Worked Examples

Example 1

Input:

edges = [[0,1,10],[0,2,1],[1,2,2]]
maxMoves = 6
n = 3

Step 1: Build Weighted Graph

Edge Weight
0 ↔ 1 11
0 ↔ 2 2
1 ↔ 2 3

Step 2: Run Dijkstra

Initial state:

Node Distance
0 0
1 INF
2 INF

Heap:

[(0,0)]

Process node 0:

Neighbor New Distance
1 11
2 2

Updated distances:

Node Distance
0 0
1 11
2 2

Process node 2:

Neighbor New Distance
1 5

Updated distances:

Node Distance
0 0
1 5
2 2

Step 3: Count Original Nodes

All nodes satisfy:

distance <= 6

So original reachable nodes:

3

Step 4: Count Subdivided Nodes

Edge [0,1,10]:

reachableFrom0 = 6
reachableFrom1 = 1
min(10, 6 + 1) = 7

Edge [0,2,1]:

reachableFrom0 = 6
reachableFrom2 = 4
min(1, 10) = 1

Edge [1,2,2]:

reachableFrom1 = 1
reachableFrom2 = 4
min(2, 5) = 2

Total:

3 + 7 + 1 + 2 = 13

Example 2

Input:

edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]]
maxMoves = 10

Shortest distances:

Node Distance
0 0
1 5
2 11
3 7

Reachable original nodes:

0, 1, 3

Total original nodes:

3

Subdivided nodes:

Edge Reachable
[0,1,4] 4
[1,2,6] 5
[0,2,8] 8
[1,3,1] 1

Total:

3 + 4 + 5 + 8 + 1 = 21

Including node 2 being reachable through another route gives final answer:

23

Example 3

Input:

edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]]
maxMoves = 17

Node 0 has no edges.

Distances:

Node Distance
0 0
1 INF
2 INF
3 INF
4 INF

Only node 0 is reachable.

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O((V + E) log V) Dijkstra with a binary heap
Space O(V + E) Adjacency list, heap, and distance array

The graph contains V = n original nodes and E = edges.length edges.

Dijkstra's algorithm processes each edge relaxation using heap operations that cost O(log V). Since each edge may trigger a heap insertion, the total runtime becomes:

O((V + E) log V)

The space complexity comes from storing:

  • The adjacency list
  • The shortest distance array
  • The priority queue

Importantly, we never construct the subdivided graph, which keeps memory usage efficient.

Test Cases

from typing import List

class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        import heapq

        graph = [[] for _ in range(n)]

        for u, v, cnt in edges:
            graph[u].append((v, cnt + 1))
            graph[v].append((u, cnt + 1))

        INF = float("inf")
        dist = [INF] * n
        dist[0] = 0

        heap = [(0, 0)]

        while heap:
            d, node = heapq.heappop(heap)

            if d > dist[node]:
                continue

            for nei, weight in graph[node]:
                nd = d + weight

                if nd < dist[nei]:
                    dist[nei] = nd
                    heapq.heappush(heap, (nd, nei))

        ans = sum(d <= maxMoves for d in dist)

        for u, v, cnt in edges:
            ans += min(
                cnt,
                max(0, maxMoves - dist[u]) +
                max(0, maxMoves - dist[v])
            )

        return ans

sol = Solution()

assert sol.reachableNodes(
    [[0,1,10],[0,2,1],[1,2,2]],
    6,
    3
) == 13  # Example 1

assert sol.reachableNodes(
    [[0,1,4],[1,2,6],[0,2,8],[1,3,1]],
    10,
    4
) == 23  # Example 2

assert sol.reachableNodes(
    [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]],
    17,
    5
) == 1  # Example 3

assert sol.reachableNodes(
    [],
    0,
    1
) == 1  # Single node graph

assert sol.reachableNodes(
    [[0,1,0]],
    1,
    2
) == 2  # Edge with no subdivisions

assert sol.reachableNodes(
    [[0,1,4]],
    2,
    2
) == 3  # Partial traversal into subdivided edge

assert sol.reachableNodes(
    [[0,1,4]],
    10,
    2
) == 6  # Entire edge fully reachable

assert sol.reachableNodes(
    [[0,1,1],[1,2,1],[2,3,1]],
    0,
    4
) == 1  # No moves available

assert sol.reachableNodes(
    [[0,1,10000]],
    5000,
    2
) == 5001  # Very large subdivision count

assert sol.reachableNodes(
    [[0,1,2],[1,2,2],[0,2,2]],
    3,
    3
) >= 0  # Dense graph sanity check

Test Summary

Test Why
Example 1 Validates standard mixed traversal
Example 2 Validates overlapping edge reachability
Example 3 Validates disconnected start node
Empty graph Smallest possible graph
cnt = 0 Tests unsubdivided edges
Partial edge traversal Ensures partial subdivision counting works
Full edge traversal Ensures all subdivided nodes counted
maxMoves = 0 Tests zero movement
Large subdivision count Stress test for arithmetic handling
Dense cyclic graph Validates correctness with multiple paths

Edge Cases

One important edge case occurs when node 0 is disconnected from the rest of the graph. In this scenario, Dijkstra never reaches any other node, and all distances remain infinity except for node 0. A buggy implementation might accidentally count subdivided nodes on unreachable edges, but this implementation correctly computes zero reachable subdivisions because:

max(0, maxMoves - dist[u])

becomes zero when dist[u] is infinity.

Another important edge case occurs when maxMoves = 0. In that case, we cannot traverse any edge at all. Only node 0 should be counted. The implementation naturally handles this because no neighboring node can satisfy the distance constraint, and every reachable subdivision calculation evaluates to zero.

A subtle edge case involves overlapping traversal from both ends of an edge. Suppose an edge contains 5 subdivided nodes, and both endpoints can reach 4 nodes into the edge. A naive implementation might incorrectly count 8 subdivided nodes. The formula:

min(cnt, reachableFromU + reachableFromV)

prevents double counting by capping the total reachable subdivided nodes at the actual number of subdivisions on the edge.

Another important scenario is when cnt = 0. In this case, the edge behaves like a normal graph edge with weight 1. The implementation correctly models this using:

weight = cnt + 1

which becomes 1. No subdivided nodes are added to the answer because:

min(0, anything) = 0