797. All Paths From Source to Target | LeetCode Medium | Python Solution | Graph, DFS, BFS

Leetcode medium problem 797. All Paths From Source to Target, detailed explanation and solution in python language.

#leetcode #python #solution

Problem Statement:
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]).
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given a directed acyclic graph of n nodes, in the form of an array of arrays.
ie, if the given graph is this, then we have total number of nodes n equal to 4.
and these nodes are labelled from index 0 to (n-1).

here, from node 0, we have directed edges to the nodes 1, 2 and 3.
from node 1, we have a directed edge to the node 3.
from node 2, we have a directed edge to the node 3.
from node 3, we have no directed edges.

one thing to note here is that, since this is acyclic directed graph, there won't be any cycles in the graph or self loops.

what we need to find out here is, all the paths starting from the first node to the last node. ie all the paths starting from the node 0 to the node 3.

for example, in this case, the paths will be [0,2,3], [0,3] and [0,1,3].

now lets look at, how we can solve this problem.

what we can do is, we will start the traversal from the first node 0.
so the current node is 0.
also, we will be recording the path we are taking, at each step.
from this node, one by one, we will move to the nodes this node is directed to.

first we will move to 1.
now, from 1, we are directed to the node 3.
and we know that, (n-1)=3 is the last node in the graph.
so this path is completed and therefore we will store it in the result.

now, lets take the next directed node 2.
from node 2, we are directed to the node 3.
since node 3 is the last node, the current path is completed and we will store it in the result.

now, lets take the next directed node 3.
since node 3 is the last node, the current path is completed and we will store it in the result.

so, this is the final result we have.

now lets code the solution.

we will store the number of nodes in this variable.

we will create an array for storing the results, and at last, we will be returning it.

for traversing through the graph till the last node, we will write a seperate function.

we will be calling this function with the first node 0, and we will be starting with the path 0.

we know that, if we have reached the last node (n-1), then the path is completed, and therefore we can add the path to the result, and return from the function.

else, we can move on to the next nodes, the current node is directed to.

for each next node, we will be passing on the path we have covered till the current node.