#797

Medium

auto_awesomeGraph traversal with depth-first search

LeetCode Problem Workspace

All Paths From Source to Target

Find all paths in a directed acyclic graph (DAG) from source to target using depth-first search and backtracking.

backtracking depth first search breadth first search graph

Problem Statement

You are given a directed acyclic graph (DAG) with nodes labeled from 0 to n - 1. Your goal is to find all possible paths from node 0 to node n - 1. The graph is represented as an adjacency list where graph[i] contains all nodes reachable from node i. Return all such paths from node 0 to node n - 1.

The input graph will be a valid DAG, ensuring no cycles. There will be no self-loops, and each list graph[i] contains unique nodes. You need to ensure all paths are found, and the paths must be in any order.

Examples

Example 1

Input: graph = [[1,2],[3],[3],[]]

Output: [[0,1,3],[0,2,3]]

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]]

Example details omitted.

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.

Solution Approach

Depth-First Search (DFS)

Use DFS to explore all paths from node 0 to node n - 1. Begin at node 0 and recursively visit all adjacent nodes. Keep track of the current path and backtrack when you reach a dead-end or node n - 1. This approach ensures that all possible paths are explored.

Backtracking

Apply backtracking to solve this problem efficiently. Start from the source node, append each visited node to the current path, and backtrack when necessary. Once you reach the target node n - 1, add the path to the result. This helps handle all edge cases while avoiding revisiting nodes unnecessarily.

Breadth-First Search (BFS)

While DFS is the natural choice for pathfinding, BFS can be an alternative. BFS can be used by iterating through nodes level by level, storing paths as you go. Each path is constructed incrementally, but it may not be as efficient as DFS for this particular task.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution is O(2^n), where n is the number of nodes. This is because, in the worst case, every possible path needs to be explored. The space complexity is O(n) due to the recursive stack and storage of paths.

What Interviewers Usually Probe

Candidates should demonstrate understanding of graph traversal, especially DFS and backtracking.
Check if the candidate can handle path construction and backtracking efficiently.
Ensure the candidate explains edge cases, such as when no path exists or when the graph is fully connected.

Common Pitfalls or Variants

Common pitfalls

Overcomplicating the solution with unnecessary algorithms like BFS when DFS is sufficient.
Failing to handle the backtracking step correctly, leading to missing paths.
Not managing memory effectively for larger graphs, which could cause stack overflow or excessive space usage.

Follow-up variants

Limit the number of nodes (n) to test edge cases and ensure efficient backtracking.
Modify the graph to add additional constraints, like limiting path lengths or adding weighted edges.
Implement a variant where paths must be ordered based on node labels.

FAQ

What is the primary pattern for solving 'All Paths From Source to Target'?

The primary pattern is graph traversal using depth-first search (DFS) with backtracking.

Can breadth-first search (BFS) be used for this problem?

Yes, BFS can be used as an alternative, but DFS is more natural and efficient for pathfinding in a DAG.

What is the time complexity of the solution?

The time complexity is O(2^n), where n is the number of nodes in the graph.

How does GhostInterview assist in solving graph traversal problems?

GhostInterview provides step-by-step guidance and helps identify efficient algorithms like DFS and backtracking for graph traversal problems.

What are common mistakes in solving this problem?

Common mistakes include using BFS unnecessarily, not handling backtracking correctly, and inefficiently managing memory for larger graphs.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        q = deque([[0]])
        ans = []
        while q:
            path = q.popleft()
            u = path[-1]
            if u == n - 1:
                ans.append(path)
                continue
            for v in graph[u]:
                q.append(path + [v])
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        n = len(graph)
        q = deque([[0]])
        ans = []
        while q:
            path = q.popleft()
            u = path[-1]
            if u == n - 1:
                ans.append(path)
                continue
            for v in graph[u]:
                q.append(path + [v])
        return ans

Continue Practicing

#802 find eventual safe states #787 cheapest flights within k stops #785 is graph bipartite