Leetcode #1059: All Paths from Source Lead to Destination
In this guide, we solve Leetcode #1059 All Paths from Source Lead to Destination in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Medium
- Premium: Yes
- Tags: Graph, Topological Sort
Intuition
The data forms a graph, so we should explore nodes and edges systematically.
A traversal ensures we visit each node once while maintaining the needed state.
Approach
Build an adjacency list and traverse with BFS or DFS.
Aggregate results as you visit nodes.
Steps:
- Build the graph.
- Traverse with BFS/DFS.
- Accumulate the required output.
Example
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.
Python Solution
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)
Complexity
The time complexity is , where and are the number of nodes and edges, respectively. The space complexity is , used to store the graph's adjacency list and state array.
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.