797. All Paths From Source to Target
Problem Description
The problem presents us with a directed acyclic graph (DAG) that consists of n
nodes labeled from 0
to n - 1
. The goal is to find all the distinct paths that lead from node 0
to node n - 1
and return the collection of these paths. The definition of the graph is such that for every node i
, there is a list of nodes, graph[i]
, that can be reached directly from node i
through a directed edge. In simple terms, if we can travel from node i
to node j
, then j
would be included in the list that corresponds with graph[i]
. Since the graph is a DAG, there are no cycles, meaning we won't revisit any node once visited on the same path, which simplifies the traversal process.
Flowchart Walkthrough
Let's analyze the problem using the Flowchart. Here's a step-by-step guide to determine the appropriate algorithm for LeetCode Problem 797: All Paths From Source to Target.
Is it a graph?
- Yes: The problem explicitly involves navigating from a source node to a target node within a directed acyclic graph (DAG).
Is it a tree?
- No: Although a tree is a type of graph, the problem's graph can contain forks (multiple choices from a single node), which isn't characteristic of trees.
Is the problem related to directed acyclic graphs (DAGs)?
- Yes: The problem's graph is specifically described as a DAG.
Does the problem involve finding topological sorts?
- No: We need to find all possible paths from source to target, not sort the nodes.
Is the problem related to shortest paths?
- No: The requirement is to list all paths, not find the shortest.
Conclusion: Based on the flowchart, the problem suits the Depth-First Search (DFS) strategy because it involves exploring all paths in a graph structure which is specifically a DAG. DFS is particularly handy to track paths and backtrack when necessary (e.g., when you hit a dead end or reach the target), which effectively gathers all possible paths in the structured order needed.
Intuition
The key insight to solving this problem lies in understanding that since the graph is acyclic, we can explore it without worrying about getting stuck in a cycle. This allows us to employ depth-first search (DFS) or breadth-first search (BFS) strategies to traverse the graph from the start node (node 0) to the end node (node n - 1
).
The provided solution uses BFS. The idea behind BFS is to explore the graph level by level, starting from the source node. Here, we initiate a queue (FIFO structure) to keep track of the paths as we discover them. We start by enqueuing the path containing just the source node [0]
.
For each path taken out of the queue, we look at the last node in the path (current node) and explore all the nodes connected to it as follows:
- If the current node is our destination node (
n - 1
), we've found a complete path from source to destination, so we add it to our list of answers. - If it's not the destination, we append each neighbor of the current node to a new path and enqueue these new paths back into the queue to be explored later.
This process is repeated until there are no more paths in the queue, meaning we've explored all possible paths from the source to the destination. At the end of this process, the ans
list contains all unique paths from node 0
to node n - 1
, and we return it as the final result.
Learn more about Depth-First Search, Breadth-First Search, Graph and Backtracking patterns.
Solution Approach
The given solution employs BFS, a common algorithm used for graph traversal that explores neighbors of a node before moving on to the next level of neighbors. In this approach, a queue is vital, which in Python, can be efficiently implemented using the collections.deque
allowing for fast appends and pops from both ends.
Here are the steps involved in the solution:
-
Initialize a queue
q
and push the path containing the start node[0]
onto it. -
Create a list
ans
to store the answer - all the paths from source to target. -
While the queue
q
is not empty, repeat the following steps:- Pop the first path from the left of the queue (using
popleft()
). - Get the last node in the path (current node
u
). - If
u
is equal ton - 1
(target node), then the path is a complete path from source to target. It's then added to theans
list. - If
u
is not the target, for each neighborv
ofu
, create a new path that extends the current path byv
and enqueue it back into the queueq
for further exploration.
- Pop the first path from the left of the queue (using
-
Continue this process until the queue is empty, which means all paths have been explored.
-
Return the
ans
list containing all the successful paths.
By using BFS and a queue, we ensure that each node in a path is only visited once and that all paths are explored systematically. It guarantees that when we reach node n - 1
, the path we have constructed is a valid path from node 0
to node n - 1
, and since there are no cycles in a DAG, each path we discover is guaranteed to be a simple path (no repeated nodes).
The use of a path list that is extended and queued at each step avoids mutating any shared state, ensuring that paths discovered in parallel do not interfere with each other. Each discovered path is independent and can be appended to the ans
list without any additional checks for validity, since the BFS approach inherently takes care of ensuring that a path is not revisited.
In summary, the BFS-based solution is an efficient way to traverse the graph and find all paths from the source to the destination in a DAG.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Given a directed acyclic graph (DAG) defined as graph = [[1,2], [3], [3], []]
, let's illustrate how the provided BFS solution approach would find all distinct paths from node 0
to node 3
.
-
Start by initializing the queue
q
with the path containing just the start node[0]
. Therefore,q = [[0]]
. -
The list
ans
to store the answers is initialized as empty:ans = []
.
Now, we start the BFS process:
-
q
is[0]
. We take out[0]
for processing (dequeue operation). -
The last node in the path
[0]
is0
. Since0
is not the target node (3
), we look at its neighbors. -
According to
graph[0]
, the neighbors are[1, 2]
. So we append each of these to our current path and add these new paths to the queue. Nowq
looks like[[0, 1], [0, 2]]
.
We repeat these steps until the queue is empty:
-
Process
[0, 1]
. This path ends in1
, which is not the target.-
Check neighbors of
1
, which only includes[3]
. -
Append
3
to our path, resulting in[0, 1, 3]
, and add it to theans
list since3
is the target. Queueq
is now[[0, 2]]
.
-
-
Process
[0, 2]
. This path ends in2
, which is not the target.-
Check neighbors of
2
, which only includes[3]
. -
Append
3
to our path, resulting in[0, 2, 3]
, and add it to theans
list. The queueq
is now empty.
-
Now that the queue q
is empty, weāve finished exploring all paths, and the process is complete. The list ans
contains all complete paths: ans = [[0, 1, 3], [0, 2, 3]]
.
Each list within ans
represents a distinct path from node 0
to node 3
. Hence, the paths are:
- Path 1: 0 -> 1 -> 3
- Path 2: 0 -> 2 -> 3
These two paths represent all the unique paths through the graph from the start node to the end node, and this is the final answer returned by the BFS approach.
Solution Implementation
1from collections import deque # Import deque from collections module for efficient queue operations
2
3class Solution:
4 def allPathsSourceTarget(self, graph):
5 # Determine the number of nodes in the graph
6 num_nodes = len(graph)
7
8 # Initialize a queue with the path starting from node 0
9 queue = deque([[0]])
10
11 # List to store all possible paths from source to target
12 all_paths = []
13
14 # Perform Breadth-First Search
15 while queue:
16 # Get the first path from the queue
17 current_path = queue.popleft()
18
19 # Access the last node in the current_path
20 last_node = current_path[-1]
21
22 # If the last node is the target node (last node in graph), append the path to all_paths
23 if last_node == num_nodes - 1:
24 all_paths.append(current_path)
25 continue
26
27 # Explore each neighbor of the last node
28 for neighbor in graph[last_node]:
29 # Append the neighbor to the current path and add the new path to the queue
30 queue.append(current_path + [neighbor])
31
32 # Return the list of all paths from source to target
33 return all_paths
34
1import java.util.*;
2
3class Solution {
4 // Function to find all paths from source (node 0) to target (last node)
5 public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
6 int n = graph.length; // The number of vertices in the graph
7 Queue<List<Integer>> queue = new LinkedList<>(); // Queue to hold the paths to be explored
8 queue.offer(Arrays.asList(0)); // Initialize queue with path starting from node 0
9 List<List<Integer>> allPaths = new ArrayList<>(); // List to store all the paths from source to target
10
11 // Process paths in the queue
12 while (!queue.isEmpty()) {
13 List<Integer> path = queue.poll(); // Retrieve and remove the head of the queue
14 int lastNode = path.get(path.size() - 1); // Get the last node in the path
15
16 // If the last node is the target, add the path to the result
17 if (lastNode == n - 1) {
18 allPaths.add(path);
19 } else {
20 // Explore all the neighbors of the last node
21 for (int neighbor : graph[lastNode]) {
22 List<Integer> newPath = new ArrayList<>(path); // Make a copy of the current path
23 newPath.add(neighbor); // Add neighbor to the new path
24 queue.offer(newPath); // Add the new path to the queue
25 }
26 }
27 }
28
29 return allPaths; // Return the list of all paths from source to target
30 }
31}
32
1#include <vector>
2
3using namespace std;
4
5class Solution {
6public:
7 vector<vector<int>> adjacencyList; // Graph representation as an adjacency list
8 vector<vector<int>> allPaths; // To store all paths from source to target
9
10 // Function to find all paths from source to target in a directed graph
11 vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
12 adjacencyList = graph; // Initialize the adjacency list with the graph
13 vector<int> currentPath; // Current path being explored
14 currentPath.push_back(0); // Start from node 0, as per problem statement
15 depthFirstSearch(0, currentPath); // Begin DFS from node 0
16 return allPaths; // Return all the computed paths after DFS completion
17 }
18
19 // Recursive function to perform depth-first search
20 void depthFirstSearch(int nodeIndex, vector<int> currentPath) {
21 // Base case: If the current node is the last node in the graph
22 if (nodeIndex == adjacencyList.size() - 1) {
23 allPaths.push_back(currentPath); // Add current path to all paths
24 return; // End recursion
25 }
26
27 // Recursive case: Explore all the adjacent nodes
28 for (int adjacentNode : adjacencyList[nodeIndex]) {
29 currentPath.push_back(adjacentNode); // Add adjacent node to current path
30 depthFirstSearch(adjacentNode, currentPath); // Recurse with new node
31 currentPath.pop_back(); // Remove the last node to backtrack
32 }
33 }
34};
35
1// Define the function to find all paths from the source (node 0) to the target (last node).
2// This function takes a graph represented as an adjacency list and returns an array of paths.
3// The graph is an array where graph[i] contains a list of all nodes that node i is connected to.
4function allPathsSourceTarget(graph: number[][]): number[][] {
5 // Initialize the array to hold all possible paths.
6 const paths: number[][] = [];
7 // Create a temporary path starting with node 0 (the source).
8 const path: number[] = [0];
9
10 // Define the depth-first search function.
11 // The 'currentPath' parameter represents the current path being explored.
12 const dfs = (currentPath: number[]) => {
13 // Get the last node from the current path.
14 const currentNode: number = currentPath[currentPath.length - 1];
15 // Check if the current node is the target node (last node in the graph).
16 if (currentNode === graph.length - 1) {
17 // If we've reached the target, add a copy of the current path to the paths array.
18 paths.push([...currentPath]);
19 return;
20 }
21 // Iterate over all neighboring nodes connected to the current node.
22 for (const nextNode of graph[currentNode]) {
23 // Add the neighbor node to the current path.
24 currentPath.push(nextNode);
25 // Recursively call 'dfs' with the updated path.
26 dfs(currentPath);
27 // Backtrack: remove the last node from the path to explore other paths.
28 currentPath.pop();
29 }
30 };
31
32 // Start the depth-first search with the initial path.
33 dfs(path);
34 // Return all the paths found.
35 return paths;
36}
37
Time and Space Complexity
The provided code is designed to find all paths from the source node (0) to the target node (n - 1
) in a directed acyclic graph (DAG). Here is an analysis of its time and space complexity:
Time Complexity
The worst-case time complexity is determined by the number of paths and the operations performed on each path. In the worst case, each node except the last can have an edge to every other node, resulting in an exponential number of paths, specifically O(2^(n-1))
, where n
is the number of nodes (since each node can be included or not in a path, like a binary decision).
A new list is created for every new path with the operation path + [v]
, which takes O(k)
time, where k
is the length of the current path.
Therefore, the overall worst-case time complexity is O(2^n * n)
, because there could be 2^n
paths and each path could take up to n
time to be copied.
Space Complexity
The space complexity is influenced by two factors:
- The space needed to store all possible paths (
ans
). - The additional space needed for the queue (
q
) to store intermediate paths.
In the worst case, all possible paths from the source to the target are stored in ans
, and each path can be of length n
, leading to a space complexity of O(2^n * n)
.
The queue will also store a considerable amount of paths. However, this does not exceed the space complexity for storing all paths since it's essentially a part of the same process.
So, the space complexity of the algorithm is O(2^n * n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Want a Structured Path to Master System Design Too? Donāt Miss This!