All Paths from Source Lead to Destination

LeetCode 1059: All Paths from Source Lead to Destination Solution & Explanation

Problem Overview

TL;DR: Use Depth First Search (DFS) with three-state coloring (Unvisited, Visiting, Visited) to detect cycles and ensure all reachable paths terminate strictly at the target node.

The problem asks us to determine if, starting from a specific source node in a directed graph, every possible path we take eventually ends at the destination node. This imposes three specific conditions:

1. There is at least one path from source to destination.
2. We never get stuck at a "dead end" (a node with no outgoing edges) that is not the destination.
3. We never enter an infinite loop (cycle).

This is a classic graph reachability and validation problem, often referred to as finding "safe states" or validating strict path termination. It is a popular interview question because it tests the ability to handle cycles in directed graphs efficiently.

Brute Force Approach for All Paths from Source Lead to Destination

A naive approach would be to simulate every possible path from the source using simple recursion. For every neighbor of the current node, we recursively attempt to reach the end.

1# Pseudo-code for Naive Approach
2function solve(current_node):
3    if current_node has no neighbors:
4        return current_node == destination
5    
6    for neighbor in current_node.neighbors:
7        if not solve(neighbor):
8            return False
9    return True

Why this fails:

1. Infinite Loops (Time Limit Exceeded): If the graph contains a cycle (e.g., A -> B -> A), the simple recursion above will enter an infinite loop, causing a Stack Overflow or Time Limit Exceeded error. The problem explicitly states that cycles reachable from the source make the result false.
2. Redundant Computations: In a dense graph without cycles, the number of paths can be exponential. A node might be visited millions of times through different paths, leading to unacceptable time complexity.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

We will implement the solution using the Graph DFS - Cycle Detection pattern.

1. Graph Representation: Convert the list of edges into an adjacency list (or map) for efficient traversal.
2. State Management: Initialize an array or hash map to track the state of each node (0: Unvisited, 1: Visiting, 2: Verified).
3. DFS Function: Create a recursive function dfs(node) that returns a boolean:
   • Base Case - Cycle: If node is currently Visiting (State 1), return false (cycle detected).
   • Base Case - Memoization: If node is Verified (State 2), return true (already checked).
   • Base Case - Leaf Node: If node has no outgoing edges, return true if node == destination, otherwise false.
   • Recursive Step:
     1. Mark node as Visiting.
     2. Iterate through all neighbors. If dfs(neighbor) returns false for any neighbor, return false immediately.
     3. Mark node as Verified.
     4. Return true.
4. Invocation: Call dfs(source) and return the result. Note that we only care about the component reachable from source, so we do not need to iterate through all nodes in the graph 0 to n-1.

Execution Flow

Let's trace the algorithm with a simple example: source = 0, destination = 2, Edges: 0->1, 1->2.

1. Start: Call dfs(0).
2. Process 0:
   • State of 0 becomes Visiting (Gray).
   • Check neighbors of 0. Neighbor is 1.
   • Recurse: Call dfs(1).
3. Process 1:
   • State of 1 becomes Visiting (Gray).
   • Check neighbors of 1. Neighbor is 2.
   • Recurse: Call dfs(2).
4. Process 2:
   • State of 2 becomes Visiting (Gray).
   • 2 has no outgoing edges.
   • Check: Is 2 == destination? Yes.
   • Mark 2 as Verified (Black).
   • Return true.
5. Backtrack to 1:
   • Neighbor 2 returned true. No other neighbors.
   • Mark 1 as Verified (Black).
   • Return true.
6. Backtrack to 0:
   • Neighbor 1 returned true. No other neighbors.
   • Mark 0 as Verified (Black).
   • Return true.
7. Result: The initial call returns true.

Proof of Correctness

The algorithm produces the correct answer based on the following invariants:

1. Cycle Detection: The Visiting state ensures that if we ever encounter a node that is currently in our recursion stack, a cycle exists. Since the problem states that no path from source can enter a cycle, any such detection correctly returns false.
2. Leaf Validation: The logic explicitly checks nodes with zero out-degree. If such a node is not destination, the condition "leads to destination" is violated. This enforces that all paths terminate specifically at destination.
3. Path Completeness: By iterating through all neighbors of a node, we ensure that the condition holds for every branch of the path. If even one branch fails, the parent node is marked invalid.
4. Memoization: Once a node is marked Verified, we know all paths from it lead to destination. Re-using this result prevents redundant work without affecting correctness.

Pattern Reuse Notes

The Graph DFS - Cycle Detection pattern is highly reusable. Understanding the 3-state coloring technique is essential for solving these related LeetCode problems:

• LeetCode 207: Course Schedule: Detect if a cycle exists in the prerequisites graph. (Exactly the same cycle detection logic).
• LeetCode 210: Course Schedule II: Same as Course Schedule but requires returning the Topological Sort order.
• LeetCode 802: Find Eventual Safe States: Identify all nodes that do not lead to a cycle. This problem is nearly identical to LeetCode 1059, except it asks for all safe start nodes rather than verifying a specific source.

Reference Implementation

C++ Solution for LeetCode 1059

1class Solution {
2    // States for DFS
3    enum State { UNVISITED, VISITING, VISITED };
4
5public:
6    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
7        // Build Adjacency List
8        vector<vector<int>> adj(n);
9        for (const auto& edge : edges) {
10            adj[edge[0]].push_back(edge[1]);
11        }
12
13        vector<State> states(n, UNVISITED);
14        return dfs(adj, states, source, destination);
15    }
16
17private:
18    bool dfs(const vector<vector<int>>& adj, vector<State>& states, int curr, int dest) {
19        // Cycle detected
20        if (states[curr] == VISITING) return false;
21        
22        // Already verified safe
23        if (states[curr] == VISITED) return true;
24
25        // Leaf node check: must be destination
26        if (adj[curr].empty()) {
27            return curr == dest;
28        }
29
30        // Mark as currently visiting (Gray)
31        states[curr] = VISITING;
32
33        // Verify all outgoing paths
34        for (int neighbor : adj[curr]) {
35            if (!dfs(adj, states, neighbor, dest)) {
36                return false;
37            }
38        }
39
40        // Mark as verified (Black)
41        states[curr] = VISITED;
42        return true;
43    }
44};

Java Solution for LeetCode 1059

1import java.util.*;
2
3class Solution {
4    // 0: Unvisited, 1: Visiting, 2: Visited
5    private enum State { UNVISITED, VISITING, VISITED }
6
7    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
8        List<List<Integer>> adj = new ArrayList<>();
9        for (int i = 0; i < n; i++) {
10            adj.add(new ArrayList<>());
11        }
12        for (int[] edge : edges) {
13            adj.get(edge[0]).add(edge[1]);
14        }
15
16        State[] states = new State[n];
17        Arrays.fill(states, State.UNVISITED);
18
19        return dfs(adj, states, source, destination);
20    }
21
22    private boolean dfs(List<List<Integer>> adj, State[] states, int curr, int dest) {
23        // Cycle detected
24        if (states[curr] == State.VISITING) return false;
25        
26        // Already verified safe
27        if (states[curr] == State.VISITED) return true;
28
29        // Leaf node check
30        if (adj.get(curr).isEmpty()) {
31            return curr == dest;
32        }
33
34        // Mark as visiting
35        states[curr] = State.VISITING;
36
37        // Verify all neighbors
38        for (int neighbor : adj.get(curr)) {
39            if (!dfs(adj, states, neighbor, dest)) {
40                return false;
41            }
42        }
43
44        // Mark as verified
45        states[curr] = State.VISITED;
46        return true;
47    }
48}

Python Solution for LeetCode 1059

1from collections import defaultdict
2
3class Solution:
4    def leadsToDestination(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
5        adj = defaultdict(list)
6        for u, v in edges:
7            adj[u].append(v)
8            
9        # 0: Unvisited, 1: Visiting, 2: Visited
10        states = [0] * n
11        
12        def dfs(node):
13            # Cycle detected
14            if states[node] == 1:
15                return False
16            # Already verified
17            if states[node] == 2:
18                return True
19            
20            # Leaf node check
21            if not adj[node]:
22                return node == destination
23            
24            # Mark as visiting (Gray)
25            states[node] = 1
26            
27            # Explore all neighbors
28            for neighbor in adj[node]:
29                if not dfs(neighbor):
30                    return False
31            
32            # Mark as visited (Black)
33            states[node] = 2
34            return True
35
36        return dfs(source)