algoadvance

Leetcode 797. All Paths From Source to Target

Problem Statement

You are given a directed, acyclic graph (DAG) of n nodes labeled from 0 to n - 1, represented by a list of n lists. Each list graph[i] is a list of nodes i can travel to directly.

Your task is to find all possible paths from node 0 to node n - 1 and return them in any order.

Clarifying Questions

1. Graph Input:
   • Should I assume a valid DAG is always provided?
   • Is it guaranteed that there will always be at least one path from node 0 to node n-1?
2. Output Format:
   • Should the paths be in any specific order like lexicographical, or is any order acceptable?

Assuming the answers to these questions are yes for a valid DAG, yes for at least one path, and any order is acceptable, let’s proceed to design the solution.

Strategy

1. Depth-First Search (DFS):
   • Utilize DFS to explore all possible paths from the source node 0 to the target node n-1.
   • Use a path list to keep track of nodes in the current path.
   • Once the target node is reached, add the current path to the results list.
2. Backtracking:
   • After exploring all paths from a node, backtrack to explore alternative paths.

Code

#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    void dfs(vector<vector<int>>& graph, vector<int>& path, vector<vector<int>>& result, int node) {
        // Add node to the current path
        path.push_back(node);
        
        // If we reach the last node, add the path to the result
        if (node == graph.size() - 1) {
            result.push_back(path);
        } else {
            // Recursively visit all adjacent nodes
            for (int nextNode : graph[node]) {
                dfs(graph, path, result, nextNode);
            }
        }
        
        // Backtrack
        path.pop_back();
    }
    
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> result;
        vector<int> path;
        dfs(graph, path, result, 0);
        return result;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> graph = \{\{1, 2}, {3}, {3}, {}};
    vector<vector<int>> result = sol.allPathsSourceTarget(graph);
    
    for (const auto& path : result) {
        for (int node : path) {
            cout << node << " ";
        }
        cout << endl;
    }
    
    return 0;
}

Time Complexity

• Let V be the number of vertices and E be the number of edges in the graph.
• Time Complexity:
  • In the worst case, we explore all possible paths from the source to the target, which can be exponential in nature. Therefore, the time complexity can be represented as O(2^V * V). The 2^V part comes from the number of possible paths and V comes from the cost of copying the path to the result.
• Space Complexity:
  • The space complexity is O(V) for the recursion stack used in DFS and the path list. Additionally, we store the result, which in the worst case can have up to 2^V paths, each of length V.

This method should efficiently find all paths from the source to the target node in a DAG, adhering to the given problem’s requirements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?