797. All Paths From Source to Target

Leetcode #: 797
Name: All Paths From Source to Target
Difficulty: Medium
Url: https://leetcode.com/problems/all-paths-from-source-to-target/

Prompt

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

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.

Approach

Examining the example same example above, each of the index of the given input represents the node. For instance, at index 0, [1, 2] represents that node 0 has a directed connection to its neighbors of node 1 and 2. Similarly, for index 1, this means that node 1 has a directed connection to node 3 and so on and so forth.

We can either solve this problem implementing one of the following:

1. Breadth-First Search
2. Depth-First Search

BFS

To implement the Breadth-First approach, we’re going to implement a Queue and we’ll start with 0 or the first index if the given input is not empty. Then we’ll check if the last element within the subarray of whatever’s front of our queue is equal to the target and if not, we want to pop the subarray from our Queue. We’ll then add a subarray into our Queue representing the next node from node 0 slowly formulating a path (i.e. [0, 1], [0, 2]). We make the same check again here comparing the target value or length of the given input — 1 and the last element within the subarray (in this case, 1 and 2 respectively). None of them equal to the target so we’ll pop both of those subarrays from our Queue and proceed to add the next path (i.e. [0, 1, 3] and [0, 2, 3]). Finally, we see that the target value does equal to the last element within each path and so we’ll add each path onto our final result array and return the result array.

DFS

We can perform a DFS and formulate a path as we traverse as far as we can go until we reach our target. Our base case will be checking simply if the node that we are currently iterating is equal to our target and if so, we will append that path to a final result array. Otherwise, if the node that I’m currently iterating is not the target, we will call our DFS algorithm recursively on each of its neighbor nodes until eventually we do land on the target node.

When making the recursive call, we have to make sure that we call the DFS algorithm recursively on its neighbor and append that neighbor onto the path that will constantly be updating / extended until we finally reach our target node.

Code

Python | Time: O(V + E) | Space: O(V) | V = the total # of vertices and E = the total # of edges

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

Discord

If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub