Is All Paths From Source to Target easy or hard?

The problem is rated Medium on LeetCode. The traversal logic is straightforward if you understand DFS and backtracking, but recognizing that every path must be enumerated—and managing the path state correctly—makes it slightly more challenging for beginners.

All Paths From Source to Target Python/Java solution

Python and Java implementations typically use DFS recursion with a list representing the current path. When the traversal reaches the target node, the path is copied into the result list. The same logic works in C++, JavaScript, and other languages with minor syntax changes.

How to solve All Paths From Source to Target in O(n)?

Solving this problem in strict O(n) time is not possible because every valid path must be generated. The optimal solutions run in O(P * N), where P is the number of paths. DFS with backtracking is the most efficient practical approach because it avoids storing many partial paths at once.

What is the best approach for All Paths From Source to Target?

Depth First Search (DFS) with backtracking is the best approach. Start from node 0, recursively explore each neighbor, and maintain a path list. When the traversal reaches node n-1, store the path. The complexity is O(P * N), where P is the number of valid paths and N is the number of nodes in the graph.

Is All Paths From Source to Target asked at Google/Amazon/Meta?

This problem represents a common graph traversal pattern frequently used in interviews at companies like Amazon, Google, and Meta. Interviewers use it to evaluate DFS, backtracking, and understanding of path enumeration in directed graphs.

What data structure is used in All Paths From Source to Target?

The core data structure is an adjacency list representing the graph. DFS solutions use recursion with a dynamic path list, while BFS solutions use a queue storing partial paths. Arrays or lists store the final set of paths.

What is the time complexity of All Paths From Source to Target?

The time complexity is O(P * N). P represents the total number of distinct paths from the source to the target, and N is the maximum length of a path. Every valid path must be constructed and copied into the result list.

Description Solution Video 12:39

797. All Paths From Source to Target

Medium83.6% acceptance5 companies

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Constraints:

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i (i.e., there will be no self-loops).
All the elements of graph[i] are unique.
The input graph is guaranteed to be a DAG.

Asked at 5 companies

Bloomberg Netflix Amazon

Google Meta

Topics

12:39

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

797. All Paths From Source to Target

Asked at 5 companies

Topics

Similar problems