797. All Paths From Source to Target

Hello, reader 👋🏽 ! Welcome to day 90 of the series on Problem Solving. Through this series, I aim to pick up at least one question every day and share my approach to solving it.

Today, I will be picking up LeetCode's daily challenge problem: 797. All Paths From Source to Target.

🤔 Problem Statement

• Given a directed acyclic graph (DAG) of n nodes labelled from 0 to n - 1, find all possible paths from the 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 the node i (i.e., there is a directed edge from the node i to node graph[i][j]).

• E.g.:

    graph => [[1,2],[3],[3],[]]
    => [[0,1,3],[0,2,3]]
  
    graph = [[4,3,1],[3,2,4],[3],[4],[]]
    => [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
  

💬 Thought Process - DFS + Backtracking

• Basically, we'd have to traverse every node from 0 to n-1. We can perform a BFS or DFS traversal to do so.

• And since it's a DAG and it's guaranteed to have no cycles and loops, we need not worry about maintaining a visited set.

  • In fact, if we do maintain a visited set, then we'll not be able to complete an entire path because some nodes will be visited multiple times.

• So, we can maintain a list that would keep track of all the nodes visited so far and then traverse the neighbours of the current node, the neighbours of the neighbours of current node and so on.

• Every time we complete traversing all the paths from the current node, we will backtrack by removing the current node from the list of nodes in the path.

• And whenever we visit the last node, we can add the current list of nodes in the path to the answer.

• After traversing every path starting from 0, we just return the final list of paths.

👩🏽‍💻 Solution - DFS + Backtracking

class Solution {
    private int n;
    private List<List<Integer>> paths;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length;
        paths = new ArrayList();

        traverseNodes(0, graph, new ArrayList());

        return paths;
    }

    private void traverseNodes(int node, int[][] graph, List<Integer> path) {
        path.add(node);
        if(node == n-1) {
            paths.add(new ArrayList(path));
        }

        for(int nextNode: graph[node]) {
            traverseNodes(nextNode, graph, path);
        }

        path.remove(path.size()-1);
    }
}

• The time complexity is a bit tricky. Since we are visiting all the paths, we might visit many nodes multiple times.

• At first look, it might seem like the complexity is O(n^2). But it's not that straightforward.

• If you look carefully out of the first and last nodes, we can make choices for the remaining n-2 nodes to whether or not include them.

• Hence, for every n nodes, there might be 2^n-2 choices of paths.

• Thus, the upper bound complexity is: O(n * 2^n).

  Note: The TC is quite tricky to come up with. I referred to this post that explains the reasoning behind this time complexity in detail.

Time Complexity: O(n * 2^n)
    - n = number of nodes
Space Complexity: O(n)
    - aux stack space used and to store all nodes in a path

💬 Thought Process - BFS + Backtracking

• The problem can also be solved using BFS. We can create a custom class that keeps track of the path traversed to reach a current node.

• Every time we process the neighbours of the current node, we can add the path so far as well as the next node to be visited.

• Once the last node has been visited, whatever path we have traversed so far can be added to the final answer -- list of paths.

👩🏽‍💻 Solution - DFS + Backtracking

class NodePath {
    // holds current node
    // path used to visit the current node
    int node;
    List<Integer> path;
    NodePath(int node, List<Integer> path) {
        this.node = node;
        this.path = path;
    } 
}

class Solution {
    private int n;
    private List<List<Integer>> paths;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length;
        paths = new ArrayList();

        Queue<NodePath> nodesToProcess = new LinkedList();
        NodePath initial = new NodePath(0, new ArrayList());
        nodesToProcess.add(initial);

        while(!nodesToProcess.isEmpty()) {
            NodePath currNodePath = nodesToProcess.poll();
            int currNode = currNodePath.node;
            List<Integer> currPath = currNodePath.path;

            currPath.add(currNode);

            if(currNode == n-1) {
                paths.add(new ArrayList(currPath));
            }
            else {
                for(int nextNode: graph[currNode]) {
                    NodePath nextNodePath = new 
                        NodePath(nextNode, new ArrayList(currPath));

                    nodesToProcess.add(nextNodePath);
                }
            }
        }

        return paths;
    }
}

Time Complexity: O(n * 2^n)
    - n = number of nodes
Space Complexity: O(n * 2^n)
    - n = number of nodes
        => BFS stores all the paths while traversing the graph

• You can find the link to all the solutions on GitHub for this question here: 797. All Paths From Source to Target.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!