We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

All Paths From Source to Target

Number: 813

Difficulty: Medium

Paid? No

Companies: Bloomberg, Amazon, Microsoft, Apple

Problem Description

Given a directed acyclic graph (DAG) with n nodes labeled from 0 to n - 1, where graph[i] is a list of all nodes that can be visited from node i, the task is to find all possible paths from node 0 to node n - 1.

Key Insights

  • The graph is a DAG, so there are no cycles. This makes a recursive Depth-First Search (DFS) or backtracking approach viable without needing to worry about infinite loops.
  • Every decision (choosing a neighbor) is independent because paths do not cycle back.
  • Backtracking is essential to explore different branches, adding a node, and later removing it to reset the current path.
  • Since the output requires listing complete paths from the source (0) to the target (n - 1), we need to store and eventually copy the current path once a valid path is found.

Space and Time Complexity

Time Complexity: O(2^n * n) in the worst-case scenario where exponential number of paths may exist, each path requiring O(n) to copy. Space Complexity: O(n) for the recursion stack and current path, excluding the space required for the output.

Solution

We can solve this problem using a Depth-First Search (DFS) algorithm with backtracking. The basic idea is to start at node 0 and explore each neighbor recursively. When the target node (n - 1) is reached, a copy of the current path is added to the result list. Once the recursive call returns, we backtrack by removing the last node so that we can continue exploring other possible paths from the previous node.

The following solutions illustrate how to implement this approach in various programming languages.

Code Solutions

def allPathsSourceTarget(graph):
    # List to store all valid paths from source to target
    result = []
    # Current path tracker
    path = []
    
    def dfs(node):
        # Add current node to the path
        path.append(node)
        # If target node is reached, add a copy of the current path to result
        if node == len(graph) - 1:
            result.append(list(path))
        else:
            # Explore all neighbors of the current node
            for neighbor in graph[node]:
                dfs(neighbor)
        # Backtrack: remove the current node before exploring a new branch
        path.pop()
    
    # Start DFS from node 0
    dfs(0)
    return result

# Example usage:
# print(allPathsSourceTarget([[1,2],[3],[3],[]]))
← Back to All Questions