Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

All Paths from Source Lead to Destination solution and explanation

MediumGraphTopological Sort5 min read37.2% acceptanceUpdated 23 Mar 2026Premium elsewhere, free here
Asked atGoogle
Practise All Paths from Source Lead to Destination
9:19
LeetCode 1059. All Paths from Source Lead to Destination Explanation and Solutionhappygirlzt · 9:19 · 4K viewsWatch on YouTube
8 more videos on this problem
  1. LeetCode 1059. All Paths from Source Lead to Destination Explanation and Solutionhappygirlzt · 9:19 · 4K views
  2. Leetcode 1059 - All Paths from Source Lead to DestinationThe Coachable Dev · 10:02 · 1K views
  3. All Paths From Source Lead To Destination [Premium] | DFS | Ultimate Graph Series | @InnoskritAakash Verma · 28:44 · 611 views
  4. 1059. All Paths from Source Lead to Destination (Leetcode Medium)Programming Live with Larry · 16:34 · 568 views
  5. All Paths from Source Lead to Destination｜DFS PythonEmily Bao · 12:10 · 341 views
  6. 1059. All Paths from Source Lead to Destination - Week 5/5 Leetcode April ChallengeProgramming Live with Larry · 21:27 · 203 views
  7. 1059. All Paths from Source Lead to DestinationMuerde un zombie · 8:58 · 131 views
  8. LeetCode 1059: All Paths from Source Lead to DestinationAlitaCode · 30:57 · 1 view
  9. LeetCode 1059: All Paths from Source Lead to DestinationAlitaCode · 31:33 · 1 view

The problem

Given the edges of a directed graph where edges[i] = [ai, bi] indicates there is an edge between nodes ai and bi, and two nodes source and destination of this graph, determine whether or not all paths starting from source eventually, end at destination, that is:

  • At least one path exists from the source node to the destination node
  • If a path exists from the source node to a node with no outgoing edges, then that node is equal to destination.
  • The number of possible paths from source to destination is a finite number.

Return true if and only if all roads from source lead to destination.

Example 1:

Input: n = 3, edges = [[0,1],[0,2]], source = 0, destination = 2
Output: false
Explanation: It is possible to reach and get stuck on both node 1 and node 2.

Example 2:

Input: n = 4, edges = [[0,1],[0,3],[1,2],[2,1]], source = 0, destination = 3
Output: false
Explanation: We have two possibilities: to end at node 3, or to loop over node 1 and node 2 indefinitely.

Example 3:

Input: n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], source = 0, destination = 3
Output: true

Constraints:

  • 1 <= n <= 104
  • 0 <= edges.length <= 104
  • edges.length == 2
  • 0 <= ai, bi <= n - 1
  • 0 <= source <= n - 1
  • 0 <= destination <= n - 1
  • The given graph may have self-loops and parallel edges.

Approach overview

Problem Overview: Given a directed graph, a source node, and a destination node, verify that every possible path starting from the source eventually ends at the destination. No path should end at another node, and cycles that allow infinite traversal must not exist.

Approach 1: Brute Force DFS Path Exploration (Exponential time)

Start from the source and recursively explore every outgoing edge using depth‑first search. Track the current path and stop when you reach a node with no outgoing edges. If that terminal node is not the destination, the condition fails. This method effectively enumerates paths and checks each terminal state. Time complexity can grow exponentially in dense graphs because the same subgraphs are explored repeatedly. Space complexity is O(V) for the recursion stack.

Approach 2: DFS with Graph Coloring / Cycle Detection (O(V + E))

Build an adjacency list and run DFS from the source while marking nodes with three states: unvisited, visiting, and safe. When DFS reaches a node with no outgoing edges, it must equal the destination; otherwise return false. If DFS encounters a node marked visiting, a cycle exists, which allows infinite paths and invalidates the requirement. Once all children of a node lead to the destination, mark it safe so future DFS calls reuse the result. This pruning avoids repeated exploration. Time complexity is O(V + E) with O(V) space for recursion and state tracking.

Approach 3: Reverse Graph + Topological Validation (O(V + E))

Another way to reason about the constraint is that every reachable node must eventually flow into the destination without cycles. Build the graph and analyze nodes using ideas from topological sort. Nodes that have no outgoing edges must be the destination; otherwise the condition fails immediately. You can propagate validity backward from the destination through incoming edges. If any reachable node cannot be proven to terminate at the destination, the graph violates the rule. Time complexity remains O(V + E) with O(V + E) space for adjacency structures.

The key insight is that the graph must behave like a directed acyclic funnel into the destination. Cycles break the guarantee because a path could loop forever, and dead-end nodes break it because a path stops before the destination.

Recommended for interviews: DFS with coloring is the expected approach. It shows you understand graph traversal, cycle detection, and memoization. A brute force DFS demonstrates the basic idea but wastes work by revisiting subgraphs. The optimized DFS proves correctness while keeping the complexity linear in the number of vertices and edges.

Solution

We use a state array state to record the status of each node, where:

  • State 0 indicates the node has not been visited;
  • State 1 indicates the node is currently being visited;
  • State 2 indicates the node has been visited and can lead to the destination.

First, we build the graph as an adjacency list, then perform a depth-first search (DFS) starting from the source node. During the DFS process:

  • If the current node's state is 1, it means we have encountered a cycle, and we return false directly;
  • If the current node's state is 2, it means the node has been visited and can lead to the destination, and we return true directly;
  • If the current node has no outgoing edges, we check whether it is the destination node. If so, return true; otherwise, return false;
  • Otherwise, set the current node's state to 1 and recursively visit all adjacent nodes;
  • If all adjacent nodes can lead to the destination, set the current node's state to 2 and return true; otherwise, return false.

The answer is the result of dfs(source).

The time complexity is O(n + m), where n and m are the number of nodes and edges, respectively. The space complexity is O(n + m), used to store the graph's adjacency list and state array.

class Solution:
    def leadsToDestination(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        def dfs(i: int) -> bool:
            if st[i]:
                return st[i] == 2
            if not g[i]:
                return i == destination

            st[i] = 1
            for j in g[i]:
                if not dfs(j):
                    return False
            st[i] = 2
            return True

        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
        if g[destination]:
            return False

        st = [0] * n
        return dfs(source)
class Solution {
    private List<Integer>[] g;
    private int[] st;
    private int destination;

    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        this.destination = destination;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] e : edges) {
            g[e[0]].add(e[1]);
        }
        if (!g[destination].isEmpty()) {
            return false;
        }
        st = new int[n];
        return dfs(source);
    }

    private boolean dfs(int i) {
        if (st[i] != 0) {
            return st[i] == 2;
        }
        if (g[i].isEmpty()) {
            return i == destination;
        }
        st[i] = 1;
        for (int j : g[i]) {
            if (!dfs(j)) {
                return false;
            }
        }
        st[i] = 2;
        return true;
    }
}
class Solution {
public:
    vector<vector<int>> g;
    vector<int> st;
    int destination;

    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        this->destination = destination;
        g.assign(n, {});
        for (auto& e : edges) {
            g[e[0]].push_back(e[1]);
        }
        if (!g[destination].empty()) {
            return false;
        }
        st.assign(n, 0);
        return dfs(source);
    }

    bool dfs(int i) {
        if (st[i] != 0) {
            return st[i] == 2;
        }
        if (g[i].empty()) {
            return i == destination;
        }
        st[i] = 1;
        for (int j : g[i]) {
            if (!dfs(j)) {
                return false;
            }
        }
        st[i] = 2;
        return true;
    }
};
function leadsToDestination(
    n: number,
    edges: number[][],
    source: number,
    destination: number,
): boolean {
    const g: number[][] = Array.from({ length: n }, () => []);
    for (const [a, b] of edges) {
        g[a].push(b);
    }
    if (g[destination].length > 0) {
        return false;
    }

    const st: number[] = Array(n).fill(0);

    const dfs = (i: number): boolean => {
        if (st[i] !== 0) {
            return st[i] === 2;
        }
        if (g[i].length === 0) {
            return i === destination;
        }
        st[i] = 1;
        for (const j of g[i]) {
            if (!dfs(j)) {
                return false;
            }
        }
        st[i] = 2;
        return true;
    };

    return dfs(source);
}
func leadsToDestination(n int, edges [][]int, source int, destination int) bool {
	g := make([][]int, n)
	for _, e := range edges {
		g[e[0]] = append(g[e[0]], e[1])
	}
	if len(g[destination]) > 0 {
		return false
	}

	st := make([]int, n)

	var dfs func(i int) bool
	dfs = func(i int) bool {
		if st[i] != 0 {
			return st[i] == 2
		}
		if len(g[i]) == 0 {
			return i == destination
		}
		st[i] = 1
		for _, j := range g[i] {
			if !dfs(j) {
				return false
			}
		}
		st[i] = 2
		return true
	}

	return dfs(source)
}
Try this approach in the editor

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS Path ExplorationExponentialO(V)Useful for understanding the problem or very small graphs
DFS with Graph ColoringO(V + E)O(V)Best general solution with cycle detection and memoization
Reverse Graph / Topological ValidationO(V + E)O(V + E)When reasoning about termination using topological ordering

Frequently asked questions

Is All Paths from Source Lead to Destination easy or hard?

The problem is rated Medium because it combines several graph concepts: DFS traversal, cycle detection, and validating terminal nodes. The implementation is straightforward once the state-marking strategy is understood.

All Paths from Source Lead to Destination Python/Java solution

The standard solution builds an adjacency list and performs DFS with a state array. Python implementations typically use recursion with a list for node states, while Java versions use arrays or enums to track visiting and safe nodes. Both achieve O(V + E) time complexity.

How to solve All Paths from Source Lead to Destination in O(n)?

Build an adjacency list and perform DFS starting from the source. Track node states to detect cycles and ensure that every terminal node equals the destination. Once a node is verified to lead only to the destination, cache it as safe to avoid repeated work. This ensures linear complexity O(V + E).

What is the best approach for All Paths from Source Lead to Destination?

DFS with graph coloring and cycle detection is the most reliable approach. Each node is marked as unvisited, visiting, or safe while exploring neighbors. If DFS finds a cycle or a terminal node that is not the destination, the condition fails. This method runs in O(V + E) time and avoids reprocessing nodes by memoizing safe states.

Is All Paths from Source Lead to Destination asked at Google/Amazon/Meta?

Graph traversal and cycle detection problems like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The question tests understanding of DFS, graph modeling, and correctness conditions around cycles and terminal nodes.

What data structure is used in All Paths from Source Lead to Destination?

An adjacency list is used to represent the directed graph efficiently. DFS traversal relies on recursion or an explicit stack along with a state array for cycle detection. This combination allows linear traversal and memoization of safe nodes.

What is the time complexity of All Paths from Source Lead to Destination?

The optimal DFS solution runs in O(V + E) time, where V is the number of vertices and E is the number of edges. Each node and edge is processed at most once during traversal. Space complexity is O(V) due to recursion stack and state tracking for each node.

Comments

Now write it yourselfClose this page and solve All Paths from Source Lead to Destination in the editor, without looking.
Practise All Paths from Source Lead to Destination