LeetCode 1059 - All Paths from Source Lead to Destination

This problem gives us a directed graph with n nodes labeled from 0 to n - 1. Each directed edge [a, b] means there is a one way path from node a to node b.

leetcodemediumgraph-theorytopological-sort

LeetCode Problem 1059

Difficulty: 🟡 Medium
Topics: Graph Theory, Topological Sort

Solution

Problem Understanding

This problem gives us a directed graph with n nodes labeled from 0 to n - 1. Each directed edge [a, b] means there is a one way path from node a to node b.

We are also given two special nodes:

  • source, where every path starts
  • destination, where every valid path must eventually end

The task is to determine whether all possible paths starting from source satisfy three conditions simultaneously:

  1. There exists at least one path from source to destination
  2. Every path eventually terminates at destination
  3. The total number of possible paths is finite

The third condition is extremely important because it rules out cycles that can be reached from source. If we can enter a cycle and keep traversing forever, then the number of possible paths is infinite, which immediately makes the answer false.

The graph may contain:

  • Cycles
  • Self loops
  • Parallel edges
  • Dead end nodes

A dead end node is a node with no outgoing edges. According to the problem statement, the only valid dead end is destination. If any other terminal node is reachable from source, the answer must be false.

The constraints are:

  • Up to 10^4 nodes
  • Up to 10^4 edges

This tells us we need an algorithm close to linear time. Exponential path enumeration is impossible because the number of paths can grow extremely quickly.

Several edge cases are important:

  • source itself may be a dead end
  • The graph may contain reachable cycles
  • destination may still have outgoing edges, which can create invalid paths
  • Some nodes may be disconnected entirely
  • A cycle not reachable from source does not matter

The key observation is that we do not need to enumerate all paths. Instead, we need to verify two properties:

  • No reachable path gets stuck anywhere except destination
  • No reachable cycle exists

This naturally suggests depth first search with cycle detection.

Approaches

Brute Force Approach

A brute force solution would attempt to enumerate every possible path starting from source.

The algorithm would recursively explore every outgoing edge and track the current traversal path. If it reaches a dead end node, it checks whether that node equals destination. If it encounters a cycle, it must determine that infinitely many paths exist.

This approach is theoretically correct because it directly checks every possible path. However, it becomes impractical very quickly.

The problem is that the number of distinct paths in a directed graph can grow exponentially. Even in an acyclic graph, the total number of paths may be enormous. If cycles exist, naive traversal may never terminate.

For example, consider a layered graph where each node branches into multiple successors. The number of paths explodes combinatorially.

Because the constraints allow up to 10^4 nodes and edges, brute force path enumeration is far too slow.

Optimal Approach

The optimal solution uses depth first search with node coloring, also known as DFS state marking.

The key insight is that we do not need to generate every path individually. Instead, we only need to verify whether each reachable node satisfies the required conditions.

For each node, we classify it into one of three states:

  • Unvisited
  • Currently being explored
  • Fully verified

If DFS reaches a node currently being explored, then we found a cycle reachable from source, which means infinitely many paths exist.

If DFS reaches a node with no outgoing edges, that node must equal destination.

Once a node has been completely verified, we memoize the result so future DFS calls do not recompute the same subtree.

This transforms the problem into linear graph traversal.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(path length) Enumerates all possible paths
Optimal O(V + E) O(V + E) DFS with cycle detection and memoization

Algorithm Walkthrough

  1. Build an adjacency list from the edge list.

We need fast access to all outgoing neighbors for every node. An adjacency list is the standard representation for sparse graphs and gives efficient traversal performance. 2. Check whether destination has outgoing edges.

If destination has outgoing edges, then a valid path could continue past the supposed ending node. Since every path must terminate at destination, this immediately makes the graph invalid. 3. Maintain a visitation state array.

We use three states:

  • 0 = unvisited
  • 1 = currently visiting
  • 2 = fully processed and verified

This allows efficient cycle detection. 4. Start DFS from source.

The DFS function determines whether all paths starting from the current node eventually lead to destination. 5. If the current node has no outgoing edges, verify it equals destination.

A dead end is only valid if it is exactly the destination node. 6. If we revisit a node currently marked as visiting, we found a cycle.

This means infinitely many paths are possible, so return false. 7. If a node is already fully processed, return true.

Memoization prevents repeated work and guarantees linear complexity. 8. Recursively verify every neighbor.

Every outgoing edge must lead to a valid subtree. If even one neighbor violates the rules, the current node is invalid. 9. After all neighbors succeed, mark the node as fully processed.

This means the node has been verified and can safely be reused later. 10. Return the result of DFS starting from source.

Why it works

The algorithm maintains the invariant that a node marked as fully processed has already been proven to satisfy the problem conditions.

Cycle detection guarantees there are no infinitely long paths reachable from source. Dead end validation guarantees all terminating paths end exactly at destination. Since DFS recursively checks every reachable outgoing edge, every possible path from source is validated.

Therefore, the algorithm correctly determines whether all paths from source lead to destination.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def leadsToDestination(
        self,
        n: int,
        edges: List[List[int]],
        source: int,
        destination: int
    ) -> bool:

        graph = defaultdict(list)

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

        # Destination must be a terminal node
        if graph[destination]:
            return False

        # 0 = unvisited
        # 1 = visiting
        # 2 = verified
        state = [0] * n

        def dfs(node: int) -> bool:
            # Dead end node
            if not graph[node]:
                return node == destination

            # Cycle detected
            if state[node] == 1:
                return False

            # Already verified
            if state[node] == 2:
                return True

            state[node] = 1

            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False

            state[node] = 2

            return True

        return dfs(source)

The implementation begins by constructing an adjacency list using a defaultdict(list). This allows efficient access to outgoing neighbors for every node.

Before DFS starts, the code checks whether destination has outgoing edges. If it does, then paths could continue beyond the destination, violating the problem requirements.

The state array tracks traversal progress for cycle detection and memoization. Nodes marked as 1 are currently in the recursion stack. Encountering such a node again indicates a cycle.

Inside the DFS function, the first check handles dead end nodes. If a node has no outgoing edges, it is only valid if it equals destination.

The second check detects cycles. The third check reuses previously verified results.

After marking the current node as visiting, the algorithm recursively verifies all neighbors. Every outgoing edge must satisfy the condition. If any recursive call returns False, the current node is invalid.

Once all neighbors succeed, the node is marked as verified and DFS returns True.

Go Solution

func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
	graph := make([][]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]
		graph[u] = append(graph[u], v)
	}

	// Destination must not have outgoing edges
	if len(graph[destination]) > 0 {
		return false
	}

	// 0 = unvisited
	// 1 = visiting
	// 2 = verified
	state := make([]int, n)

	var dfs func(int) bool

	dfs = func(node int) bool {
		// Dead end node
		if len(graph[node]) == 0 {
			return node == destination
		}

		// Cycle detected
		if state[node] == 1 {
			return false
		}

		// Already verified
		if state[node] == 2 {
			return true
		}

		state[node] = 1

		for _, neighbor := range graph[node] {
			if !dfs(neighbor) {
				return false
			}
		}

		state[node] = 2

		return true
	}

	return dfs(source)
}

The Go implementation follows the same logic as the Python version. The adjacency list is represented using a slice of slices.

Go does not have Python style dictionaries with automatic defaults, so we initialize graph as make([][]int, n).

The DFS function is declared as a closure using var dfs func(int) bool.

State tracking uses an integer slice exactly like the Python version.

Since Go slices default to nil, checking len(graph[node]) == 0 works correctly for dead end detection even when the slice was never initialized.

Worked Examples

Example 1

n = 3
edges = [[0,1],[0,2]]
source = 0
destination = 2

Adjacency list:

0 -> [1, 2]
1 -> []
2 -> []

DFS traversal:

Step Current Node State Array Result
1 0 [1,0,0] Start DFS
2 1 [1,0,0] Dead end
3 1 != 2 [1,0,0] Return false

Node 1 is a dead end that is not the destination, so the answer is false.

Example 2

n = 4
edges = [[0,1],[0,3],[1,2],[2,1]]
source = 0
destination = 3

Adjacency list:

0 -> [1, 3]
1 -> [2]
2 -> [1]
3 -> []

DFS traversal:

Step Current Node State Array Result
1 0 [1,0,0,0] Start DFS
2 1 [1,1,0,0] Continue
3 2 [1,1,1,0] Continue
4 1 [1,1,1,0] Cycle detected

The cycle 1 -> 2 -> 1 creates infinitely many paths, so the answer is false.

Example 3

n = 4
edges = [[0,1],[0,2],[1,3],[2,3]]
source = 0
destination = 3

Adjacency list:

0 -> [1, 2]
1 -> [3]
2 -> [3]
3 -> []

DFS traversal:

Step Current Node State Array Result
1 0 [1,0,0,0] Start DFS
2 1 [1,1,0,0] Continue
3 3 [1,1,0,0] Valid terminal
4 1 complete [1,2,0,0] Verified
5 2 [1,2,1,0] Continue
6 3 [1,2,1,0] Valid terminal
7 2 complete [1,2,2,0] Verified
8 0 complete [2,2,2,0] Success

Every possible path terminates at node 3, so the answer is true.

Complexity Analysis

Measure Complexity Explanation
Time O(V + E) Each node and edge is processed at most once
Space O(V + E) Adjacency list plus recursion stack and state array

The adjacency list stores every edge exactly once, requiring O(E) space. The state array requires O(V) space.

During DFS, each node transitions through states only once, and each edge is traversed once during recursion. Therefore, the total runtime is linear in the size of the graph.

The recursion stack may grow up to O(V) in the worst case for a deep graph.

Test Cases

from typing import List

class Solution:
    def leadsToDestination(
        self,
        n: int,
        edges: List[List[int]],
        source: int,
        destination: int
    ) -> bool:

        from collections import defaultdict

        graph = defaultdict(list)

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

        if graph[destination]:
            return False

        state = [0] * n

        def dfs(node: int) -> bool:
            if not graph[node]:
                return node == destination

            if state[node] == 1:
                return False

            if state[node] == 2:
                return True

            state[node] = 1

            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False

            state[node] = 2

            return True

        return dfs(source)

sol = Solution()

assert sol.leadsToDestination(
    3,
    [[0, 1], [0, 2]],
    0,
    2
) is False  # dead end at non-destination node

assert sol.leadsToDestination(
    4,
    [[0, 1], [0, 3], [1, 2], [2, 1]],
    0,
    3
) is False  # reachable cycle creates infinite paths

assert sol.leadsToDestination(
    4,
    [[0, 1], [0, 2], [1, 3], [2, 3]],
    0,
    3
) is True  # all paths reach destination

assert sol.leadsToDestination(
    1,
    [],
    0,
    0
) is True  # source equals destination with no edges

assert sol.leadsToDestination(
    2,
    [[0, 0]],
    0,
    1
) is False  # self-loop cycle

assert sol.leadsToDestination(
    3,
    [[0, 1], [1, 2], [2, 1]],
    0,
    2
) is False  # cycle involving destination path

assert sol.leadsToDestination(
    3,
    [[0, 1]],
    0,
    1
) is True  # single valid path

assert sol.leadsToDestination(
    3,
    [[0, 1], [1, 2], [2, 2]],
    0,
    2
) is False  # destination has self-loop

assert sol.leadsToDestination(
    5,
    [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]],
    0,
    4
) is True  # converging paths

assert sol.leadsToDestination(
    5,
    [[0, 1], [1, 2], [2, 3]],
    0,
    4
) is False  # reachable dead end before destination
Test Why
[[0,1],[0,2]] Verifies dead end detection
Cycle between 1 and 2 Verifies infinite path detection
Diamond graph to destination Verifies multiple valid paths
Single node graph Boundary case
Self loop on source Verifies cycle handling
Cycle reachable before destination Ensures infinite paths fail
Single linear path Basic correctness
Destination self loop Destination must be terminal
Converging paths Verifies memoization correctness
Missing path to destination Verifies invalid dead end handling

Edge Cases

One important edge case occurs when the source node itself is a dead end. If source has no outgoing edges, then the answer is only valid if source == destination. A naive implementation might incorrectly return true simply because traversal ends immediately. The DFS implementation handles this correctly through the dead end check.

Another important case involves reachable cycles. A cycle means there are infinitely many possible paths because traversal can continue forever. This is easy to miss if the implementation only checks whether some path reaches the destination. The visitation state array correctly detects back edges during DFS and immediately returns false.

A third subtle case is when destination itself has outgoing edges. Even if every path eventually reaches destination, the existence of outgoing edges means paths could continue past it. Since the problem requires all paths to terminate at destination, this situation must return false. The implementation explicitly checks this before DFS begins.

A fourth important edge case involves disconnected graph components. The graph may contain cycles or dead ends completely unrelated to source. These should not affect the answer. Since DFS only explores nodes reachable from source, unreachable components are naturally ignored.

A final tricky case is parallel edges. The graph may contain multiple identical directed edges between two nodes. The DFS implementation processes each edge independently, but memoization ensures nodes are not redundantly recomputed, so correctness and efficiency are preserved.