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.length2 <= n <= 150 <= graph[i][j] < ngraph[i][j] != i (i.e., there will be no self-loops).graph[i] are unique.The problem asks us to return all possible paths from node 0 (source) to node n-1 (target) in a directed acyclic graph represented as an adjacency list. Since we must explore every valid path, the most natural technique is Depth-First Search (DFS) with backtracking.
Start from node 0 and recursively explore each neighbor while maintaining the current path. Whenever the traversal reaches the target node, record the path as a valid result. Backtracking ensures that after exploring one branch, the algorithm removes the last node and continues exploring alternative routes. Because the graph is acyclic, we do not need complex cycle detection.
An alternative is a Breadth-First Search (BFS) that stores partial paths in a queue and expands them level by level until reaching the destination.
If there are P valid paths and each path has length up to N, the total work is proportional to exploring and storing these paths. Thus, the time complexity grows with the number of possible paths.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Backtracking | O(P × N) where P is number of paths and N is path length | O(N) recursion stack (excluding output) |
| BFS Path Expansion | O(P × N) | O(P × N) for storing paths in queue |
AlgosWithMichael
The Depth First Search (DFS) approach uses a recursive function to explore all paths from the source node to the target node by traversing each possible node in a depth-first manner. This involves exploring as far as possible along each branch before backing up.
Time Complexity: O(2^n) - since every node could lead to every other node, creating exponential paths.
Space Complexity: O(n) - the maximum depth of the recursion, and path storage could be O(n) as well.
1#include <stdio.h>
2#include <stdlib.h>
3
4void dfs(int node, int n, int** graph, int* graphColSize,
This C solution implements a depth-first search (DFS) recursively. The function "dfs" is called with each node and adds the node to the current path. If the current node is the target node, the path is added to the result. Otherwise, the function is called recursively for each of the node's children. Memory is dynamically allocated for the paths and adjusted for recursion depth.
The Breadth First Search (BFS) approach uses a queue to explore nodes level by level, tracking each path as it progresses. This is an iterative process that can make finding all possible paths easier to visualize compared to recursive methods like DFS.
Time Complexity: O(2^n) - Because each node may lead to different paths creating an exponential number of routes.
Space Complexity: O(2^n) - Required for holding all potential paths in the queue.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
DFS is preferred because it naturally explores one path completely before trying alternatives, which aligns well with generating full paths. BFS can also work, but it requires storing many partial paths in memory, making it less space-efficient in many cases.
Yes, variations of this problem appear in technical interviews at large tech companies. Interviewers often use it to test graph traversal concepts, recursion, and the candidate's ability to generate all possible solutions using DFS or backtracking.
An adjacency list is the best representation for the graph because it allows efficient traversal of neighbors. During DFS, a dynamic list or vector is used to track the current path, and recursion naturally manages exploration and backtracking.
The most common approach is Depth-First Search with backtracking. Starting from node 0, we explore each neighbor recursively while maintaining the current path. When we reach node n-1, we add the path to the result and backtrack to explore other possibilities.
This C solution implements Breadth First Search (BFS) using a queue to iteratively explore the graph level by level. Paths are stored in the queue and processed in FIFO order. New paths are generated for each child node, leading to either an extension to the path or storing the path if it reaches the target node.