algoadvance

Leetcode 797. All Paths From Source to Target

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 a list of lists, where graph[i] is a list of all nodes j for which the edge (i, j) exists.

Clarifying Questions

  1. Q: Can there be multiple paths from the source to the target?
    • A: Yes, and we need to find all such paths.
  2. Q: What should be the format of the output?
    • A: The output should be a list of lists, where each list represents a path from node 0 to node N-1.
  3. Q: Will the graph have cycles?
    • A: No, since the graph is a directed acyclic graph (DAG).
  4. Q: What is the maximum size of the graph?
    • A: The graph can be of size up to 15 nodes (0 to 14).

Strategy

To solve this problem, we can use Depth-First Search (DFS) to explore all paths from the source node (0) to the target node (N-1). Since the graph is a DAG, there will be no cycles, making DFS an appropriate choice.

  1. Initialization:
    • Define a method to perform the DFS traversal.
    • Use a list to keep track of the current path and a list of lists to store all the valid paths.
  2. DFS Execution:
    • Start the DFS traversal from node 0.
    • For each node, recursively explore all its neighbors.
    • If node N-1 is reached, add the current path to the list of valid paths.
    • Backtrack to explore other possible paths.
  3. Return the Results:
    • After the DFS traversal completes, return the list containing all valid paths.

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(graph, 0, path, result);
        return result;
    }
    
    private void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> result) {
        path.add(node);
        // If the current node is the target, add the path to the result
        if (node == graph.length - 1) {
            result.add(new ArrayList<>(path));
        } else {
            // Explore all the neighbors of the current node
            for (int neighbor : graph[node]) {
                dfs(graph, neighbor, path, result);
            }
        }
        // Backtrack to explore other paths
        path.remove(path.size() - 1);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = { {1, 2}, {3}, {3}, {} };
        List<List<Integer>> paths = sol.allPathsSourceTarget(graph);
        System.out.println(paths);
    }
}

Time Complexity

The time complexity of the solution is (O(2^N \cdot N)), where (N) is the number of nodes in the graph. This complexity arises because:

Explanation

  1. Initialization:
    • The allPathsSourceTarget method initializes the result list to store all paths and the path list to store the current path during the DFS traversal.
  2. DFS Execution:
    • The dfs method is a recursive helper function that explores all paths starting from the given node.
  3. Path Recording:
    • When the target node (N-1) is reached, the current path is added to the result.
  4. Backtracking:
    • After exploring all neighbors, the current node is removed from the path to allow exploration of other paths.

By utilizing DFS and backtracking, the solution efficiently finds all paths from the source to the target in the given DAG.

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