All Paths From Source to Target (DAG)

📋

Problem

Imagine navigating a city's road map where you want to find every possible route from your home to a landmark without revisiting any street.

Given a directed acyclic graph (DAG) represented as an adjacency list, find all possible paths from the source node (0) to the target node (n-1). Return a list of all paths, where each path is represented as a list of nodes.

1 ≤ n ≤ 10^5The graph is a DAG (no cycles)Each node's adjacency list contains nodes with indices in [0, n-1]The graph is represented as graph[i] = list of nodes j where there is an edge i -> j

Edge cases: Graph with only one node (0) → [[0]]Graph where source has no outgoing edges → []Graph with multiple branching paths → multiple paths returned

</>

IDE

def allPathsSourceTarget(graph: list[list[int]]) -> list[list[int]]:public List<List<Integer>> allPathsSourceTarget(int[][] graph)vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph)function allPathsSourceTarget(graph)

def allPathsSourceTarget(graph):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    // Write your solution here
    return {};
}

function allPathsSourceTarget(graph) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[0,1,3]]Greedy approach returning only first found path, missing others.✅ Explore all neighbors recursively and backtrack after each to find all paths.

Wrong: []Incorrectly returning empty when source equals target or no edges from source in single node graph.✅ Return [[0]] if graph has one node and source equals target.

Wrong: Infinite loop or stack overflowCycle in graph causing infinite recursion despite DAG assumption.✅ Add cycle detection or rely on problem constraints to avoid cycles.

Wrong: [[0,1,4]]Not copying path before appending, causing shared path mutation and missing distinct paths.✅ Append a copy of current path to results, e.g. res.append(path[:]).

Wrong: TLE or timeoutExponential time complexity due to enumerating all paths without memoization.✅ Implement DFS with memoization caching paths from each node.

✓

Test Cases

Focus on handling graphs with minimal nodes and no edges correctly.

Think about common pitfalls like greedy path selection and cycles.

Consider how to optimize your DFS to avoid exponential time complexity.

t1_01basic

Input{"graph":[[1,2],[3],[3],[]]}

Expected[[0,1,3],[0,2,3]]

⏱ Performance - must finish in 2000ms

From node 0, paths to target 3 are [0,1,3] and [0,2,3].

💡 Think about exploring all paths from source to target using DFS.

💡 Use backtracking to explore each neighbor and record paths when target is reached.

💡 Append current node to path, recurse on neighbors, then backtrack by popping.

Why it failed: Incorrect or missing paths. Likely missing backtracking or not exploring all neighbors. Fix by ensuring DFS explores all neighbors and backtracks properly.

✓ Correctly finds all paths from source to target.

t1_02basic

Input{"graph":[[4,3,1],[3,2,4],[3],[4],[]]}

Expected[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

⏱ Performance - must finish in 2000ms

Multiple paths from 0 to 4 exist, including direct and via intermediate nodes.

💡 Check all neighbors of each node recursively to find all paths.

💡 Use DFS with path tracking and backtracking to avoid missing paths.

💡 Add path to results only when target node is reached.

Why it failed: Missing some paths or incorrect paths. Possibly not exploring all neighbors or incorrect path recording. Fix by thorough DFS with backtracking and recording complete paths.

✓ All distinct paths from source to target are correctly found.

t2_01edge

Input{"graph":[[]]}

Expected[[0]]

⏱ Performance - must finish in 2000ms

Single node graph where source is also target; only one path [0].

💡 Consider the case when graph has only one node with no edges.

💡 The path should be just the single node itself.

💡 Return [[0]] when graph length is 1 and no edges exist.

Why it failed: Returns empty or no path for single node graph. Fix by handling base case where source equals target and return [[0]].

✓ Correctly returns single path for single node graph.

t2_02edge

Input{"graph":[[],[2],[],[]]}

Expected[]

⏱ Performance - must finish in 2000ms

Source node 0 has no outgoing edges, so no path to target 3 exists.

💡 Check if source node has neighbors; if none, no paths exist.

💡 DFS should return empty if no way to reach target.

💡 Return empty list if no paths found from source to target.

Why it failed: Returns non-empty paths when source has no outgoing edges. Fix by returning empty list if no neighbors to explore from source.

✓ Correctly returns empty list when no path from source to target.

t2_03edge

Input{"graph":[[1],[2],[3],[4],[]]}

Expected[[0,1,2,3,4]]

⏱ Performance - must finish in 2000ms

Linear chain from 0 to 4; only one path exists.

💡 Consider a linear chain graph where each node points to next.

💡 DFS should follow the chain until target is reached.

💡 Return the single path that includes all nodes in order.

Why it failed: Returns multiple or incomplete paths for linear chain. Fix by correctly following chain and recording full path to target.

✓ Correctly returns single path for linear chain graph.

t3_01corner

Input{"graph":[[1,2],[3],[3],[4],[]]}

Expected[[0,1,3,4],[0,2,3,4]]

⏱ Performance - must finish in 2000ms

Graph with branching paths; tests if all branches are explored.

💡 Beware of greedy approaches that pick only one neighbor.

💡 DFS must explore all neighbors to find all paths.

💡 Ensure backtracking after exploring each neighbor to explore others.

Why it failed: Greedy approach returns only one path. Fix by exploring all neighbors recursively and backtracking properly.

✓ All branching paths correctly found.

t3_02corner

Input{"graph":[[1],[2],[3],[1],[]]}

Expected[]

⏱ Performance - must finish in 2000ms

Graph contains a cycle (1->2->3->1), but problem states DAG; tests cycle detection or assumption.

💡 Problem states graph is DAG; cycles should not exist.

💡 If cycles appear, algorithm may loop infinitely.

💡 Implement visited set or rely on problem constraints to avoid cycles.

Why it failed: Algorithm loops infinitely or crashes on cycle. Fix by adding cycle detection or trusting DAG input and avoiding infinite recursion.

✓ Handles DAG assumption correctly; no infinite loops.

t3_03corner

Input{"graph":[[1,2,3],[4],[4],[4],[]]}

Expected[[0,1,4],[0,2,4],[0,3,4]]

⏱ Performance - must finish in 2000ms

Multiple paths converge to same target; tests if all distinct paths are found.

💡 Check if algorithm merges paths incorrectly losing distinctness.

💡 Each path must be recorded separately even if they share nodes.

💡 Use separate path copies when appending to results.

Why it failed: Returns fewer paths due to shared nodes. Fix by copying path list before appending to results to preserve distinct paths.

✓ All distinct converging paths correctly returned.

t4_01performance

Input{"graph":[[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11],[12],[13],[14],[15],[16],[17],[18],[19],[20],[21],[22],[23],[24],[25],[26],[27],[28],[29],[30],[31],[32],[33],[34],[35],[36],[37],[38],[39],[40],[41],[42],[43],[44],[45],[46],[47],[48],[49],[50],[51],[52],[53],[54],[55],[56],[57],[58],[59],[60],[61],[62],[63],[64],[65],[66],[67],[68],[69],[70],[71],[72],[73],[74],[75],[76],[77],[78],[79],[80],[81],[82],[83],[84],[85],[86],[87],[88],[89],[90],[91],[92],[93],[94],[95],[96],[97],[98],[99],[]]}

Expectednull

⏱ Performance - must finish in 2000ms

Linear chain graph with n=100 nodes; algorithm must run in O(V+E) time to avoid TLE.

💡 Brute force exponential path enumeration will TLE here.

💡 Use DFS with memoization to cache paths from each node.

💡 Dynamic programming or memoization reduces complexity to O(V+E+P).

Why it failed: TLE due to exponential path enumeration without memoization. Fix by implementing DFS with memoization to cache subpaths.

✓ Algorithm runs within time limits using efficient DFS with memoization.

Practice

1. Consider the following code snippet implementing the optimal solution for the largest color value in a directed graph. Given colors = "abaca" and edges = [[0,1],[0,2],[2,3],[3,4]], what is the value of max_color_value after processing all nodes?

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace dp for node 0 (color 'a')

   dp[0]['a'] = 1, max_color_value = 1

2. Step 2: Propagate to nodes 1 and 2

   Node 1 (color 'b'): dp[1]['a'] = 1, dp[1]['b'] = 1; Node 2 (color 'a'): dp[2]['a'] = 2, max_color_value = 2

3. Step 3: Propagate to node 3 (color 'c')

   dp[3]['a'] = 2, dp[3]['c'] = 1, max_color_value = 2

4. Step 4: Propagate to node 4 (color 'a')

   dp[4]['a'] = 3, max_color_value = 3

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Maximum color count along path is 3 for 'a' [OK]

Hint: Track dp updates per node carefully [OK]

Common Mistakes:

• Off-by-one in dp increments or max updates

2. Consider the following code snippet implementing the optimal solution for the longest path with different adjacent characters problem. Given n = 3, edges = [[0,1],[1,2]], and s = "aba", what is the final returned value?

easy

A. -1

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace topological order and dp array

   Topological order is [0,1,2]. Initialize dp = [1,1,1]. - For node 0: neighbor 1, s[1] = 'b' != s[0] = 'a', dp[1] = max(1, 1+1) = 2. - For node 1: neighbor 2, s[2] = 'a' != s[1] = 'b', dp[2] = max(1, 2+1) = 3.

2. Step 2: Compute final answer

   Maximum dp value is 3, which is returned.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   dp array ends as [1, 2, 3], max is 3 [OK]

Hint: Check dp updates along topo order carefully [OK]

Common Mistakes:

• Returning dp[node] instead of max(dp)
• Ignoring character difference condition
• Miscomputing topological order

3. What is the time complexity of the optimal DFS postorder topological sort approach for sequence reconstruction, given n as the length of the original sequence and m as the total length of all sequences in seqs?

medium

A. O(n + m)

B. O(n! * m)

C. O(n * m)

D. O(m^2)

Solution

1. Step 1: Identify graph construction cost

   Building graph from seqs takes O(m) time, where m is total length of all sequences.

2. Step 2: Analyze DFS traversal cost

   DFS visits each node once and edges once, total O(n + m). No extra factorial or quadratic factors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in nodes plus edges [OK]

Hint: DFS topo sort is O(V+E) -> O(n+m) here [OK]

Common Mistakes:

• Confusing with brute force factorial complexity
• Assuming quadratic due to nested loops

4. Suppose the problem is modified so that edges can be dynamically added or removed, and you need to repeatedly query which nodes are eventually safe after each update. Which approach is best suited to efficiently handle these dynamic queries?

hard

A. Maintain in-degree counts and update them incrementally, adjusting the queue of safe nodes dynamically.

B. Use a DFS with memoization approach and invalidate memoization only for affected nodes after each update.

C. Re-run the entire reversed graph + Kahn's algorithm from scratch after each update.

D. Use a brute force DFS cycle detection from every node after each update.

Solution

1. Step 1: Understand dynamic graph updates

   Recomputing from scratch is expensive; brute force DFS is too slow for repeated queries.

2. Step 2: Incremental in-degree updates

   Maintaining in-degree counts and adjusting the queue of safe nodes incrementally allows efficient updates without full recomputation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incremental updates leverage Kahn's algorithm structure for dynamic graphs [OK]

Hint: Incremental in-degree updates enable efficient dynamic queries [OK]

Common Mistakes:

• Re-running full algorithm after each update
• Using brute force DFS repeatedly
• Invalidating all memoization unnecessarily

5. Suppose the problem is modified so that nodes can be revisited multiple times (cycles allowed), but the path must still have no two adjacent nodes with the same character. Which approach correctly adapts the solution?

hard

A. Switch to DFS with cycle detection and memoization to handle revisits and character constraints

B. Use the same topological sort + DP approach, ignoring cycles since character constraints prevent infinite loops

C. Apply Bellman-Ford algorithm to detect negative cycles and compute longest paths

D. Use iterative DP on topological order but reset dp values when cycles are detected

Solution

1. Step 1: Understand impact of cycles

   Topological sort is invalid with cycles, so iterative DP on topo order cannot be applied.

2. Step 2: Choose correct approach

   DFS with cycle detection and memoization can explore paths safely, avoiding infinite recursion and respecting character constraints.

3. Step 3: Why other options fail

   Ignoring cycles or resetting dp is incorrect; Bellman-Ford is for shortest paths and not suited here.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DFS with cycle detection handles cycles and constraints correctly [OK]

Hint: Cycles break topo sort; use DFS with cycle detection [OK]

Common Mistakes:

• Trying to apply topological sort on cyclic graphs
• Ignoring cycle detection leading to infinite loops
• Misapplying shortest path algorithms