LeetCode 797: All Paths From Source to Target Solution
Master LeetCode problem 797 (All Paths From Source to Target), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
797. All Paths From Source to Target
Problem Explanation
Explanation
To find all possible paths from node 0 to node n-1 in a directed acyclic graph (DAG), we can perform a depth-first search (DFS) starting from node 0. We will keep track of the current path being explored and when reaching node n-1, we will add the current path to the result.
Algorithm
- Initialize an empty list to store all paths.
- Perform a DFS starting from node 0.
- During DFS, keep track of the current path being explored.
- When reaching node n-1, add the current path to the result.
- Recursively explore all neighbors of the current node.
- Backtrack by removing the last node from the current path.
Time Complexity
The time complexity is O(2^N) in the worst case, where N is the number of nodes in the graph.
Space Complexity
The space complexity is O(N) for the recursion stack and the paths stored.
Solution Code
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> paths = new ArrayList<>();
List<Integer> currentPath = new ArrayList<>();
dfs(0, graph, currentPath, paths);
return paths;
}
private void dfs(int node, int[][] graph, List<Integer> currentPath, List<List<Integer>> paths) {
currentPath.add(node);
if (node == graph.length - 1) {
paths.add(new ArrayList<>(currentPath));
} else {
for (int neighbor : graph[node]) {
dfs(neighbor, graph, currentPath, paths);
}
}
currentPath.remove(currentPath.size() - 1);
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 797 (All Paths From Source to Target)?
This page provides optimized solutions for LeetCode problem 797 (All Paths From Source to Target) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 797 (All Paths From Source to Target)?
The time complexity for LeetCode 797 (All Paths From Source to Target) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 797 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 797 in Java, C++, or Python.