All Paths From Source to Target (DAG)

▶

Steps

setup

Initialize stack with source node and path

We start by setting the target node to 3 and initializing the stack with the tuple (0, [0]), representing the source node and the path containing only itself.

💡 This sets up the starting point for DFS traversal and path tracking.

Line:

target = len(graph) - 1
res = []
stack = [(0, [0])]

💡 The stack holds nodes to explore along with the path taken to reach them.

traverse

Pop node 0 and path [0] from stack

We pop the top element from the stack, which is node 0 with path [0]. Node 0 is now being processed.

💡 Popping from the stack means we are exploring this node's neighbors next.

Line:

node, path = stack.pop()

💡 The algorithm explores neighbors of the current node to extend paths.

expand

Push neighbor 2 with path [0,2] onto stack

We push neighbor 2 of node 0 onto the stack with the updated path [0,2]. This path represents going from 0 to 2.

💡 Adding neighbors to the stack extends the search paths for DFS.

Line:

for nei in graph[node]:
    stack.append((nei, path + [nei]))

💡 Stack order affects traversal order; last pushed neighbor is explored first.

expand

Push neighbor 1 with path [0,1] onto stack

Next, we push neighbor 1 of node 0 onto the stack with the updated path [0,1]. This path represents going from 0 to 1.

💡 Neighbors are pushed in order to ensure DFS explores node 1 after node 2.

Line:

for nei in graph[node]:
    stack.append((nei, path + [nei]))

💡 Stack LIFO order means neighbor 1 will be popped after neighbor 2.

traverse

Pop node 1 and path [0,1] from stack

We pop node 1 with path [0,1] from the stack to explore its neighbors.

💡 Exploring node 1 extends paths towards the target.

Line:

node, path = stack.pop()

💡 The algorithm continues DFS by exploring neighbors of node 1.

expand

Push neighbor 3 with path [0,1,3] onto stack

We push neighbor 3 of node 1 onto the stack with the updated path [0,1,3]. This path reaches the target node.

💡 Adding neighbor 3 extends the path to the target, ready to be collected.

Line:

for nei in graph[node]:
    stack.append((nei, path + [nei]))

💡 Paths are built incrementally by adding neighbors to the stack.

traverse

Mark node 1 done after pushing neighbors

After pushing all neighbors of node 1, we mark node 1 as done to indicate it has been fully processed.

💡 Marking done helps track which nodes have been fully explored.

Line:

else:
    for nei in graph[node]:
        stack.append((nei, path + [nei]))

💡 Node states help visualize traversal progress.

traverse

Pop node 3 and path [0,1,3] from stack (target reached)

We pop node 3 with path [0,1,3] from the stack. Since node 3 is the target, we add this path to the results.

💡 Finding the target means a complete path is discovered and saved.

Line:

node, path = stack.pop()
if node == target:
    res.append(path)

💡 The algorithm collects all complete paths as soon as they reach the target.

traverse

Mark node 3 done after adding path

After adding the path ending at node 3, we mark node 3 as done since it has no neighbors.

💡 Nodes with no neighbors are terminal and marked done immediately.

Line:

if node == target:
    res.append(path)

💡 Terminal nodes finalize paths and are fully processed.

traverse

Pop node 2 and path [0,2] from stack

We pop node 2 with path [0,2] from the stack to explore its neighbors.

💡 Exploring node 2 extends paths towards the target.

Line:

node, path = stack.pop()

💡 DFS continues exploring all neighbors to find all paths.

expand

Push neighbor 3 with path [0,2,3] onto stack

We push neighbor 3 of node 2 onto the stack with the updated path [0,2,3], another path reaching the target.

💡 Adding neighbor 3 extends the second path to the target.

Line:

for nei in graph[node]:
    stack.append((nei, path + [nei]))

💡 All paths are explored by pushing neighbors with updated paths.

traverse

Mark node 2 done after pushing neighbors

After pushing all neighbors of node 2, we mark node 2 as done to indicate it has been fully processed.

💡 Marking done helps track which nodes have been fully explored.

Line:

else:
    for nei in graph[node]:
        stack.append((nei, path + [nei]))

💡 Node states help visualize traversal progress.

traverse

Pop node 3 and path [0,2,3] from stack (target reached)

We pop node 3 with path [0,2,3] from the stack. Since node 3 is the target, we add this path to the results.

💡 Finding the target means a complete path is discovered and saved.

Line:

node, path = stack.pop()
if node == target:
    res.append(path)

💡 The algorithm collects all complete paths as soon as they reach the target.

traverse

Mark node 3 done after adding second path

After adding the second path ending at node 3, we mark node 3 as done again to confirm full processing.

💡 Terminal nodes finalize paths and are fully processed.

Line:

if node == target:
    res.append(path)

💡 Terminal nodes finalize paths and are fully processed.

reconstruct

Stack empty, return all collected paths

The stack is now empty, meaning all paths have been explored. We return the collected results [[0,1,3],[0,2,3]].

💡 Returning results completes the algorithm, showing all paths found.

Line:

return res

💡 The algorithm successfully found all paths from source to target.

from typing import List

def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
    target = len(graph) - 1  # STEP 1
    res = []  # STEP 1
    stack = [(0, [0])]  # STEP 1

    while stack:  # STEP 2 loop
        node, path = stack.pop()  # STEP 2
        if node == target:  # STEP 8,13
            res.append(path)  # STEP 8,13
        else:  # STEP 3,6,11
            for nei in graph[node]:  # STEP 3,6,11
                stack.append((nei, path + [nei]))  # STEP 3,6,11
    return res  # STEP 15

📊

All Paths From Source to Target (DAG) - Watch the Algorithm Execute, Step by Step

Watching each stack operation and path extension helps you understand how DFS explores all routes in a DAG without recursion.

Visiting: 0

0

1

2

3

Queue / Stack

0 - path: [0]

Visiting: 0

0

1

2

3

Visiting: 0

Edge: 0 → 2

0

1

2

3

Queue / Stack

2 - path: [0,2]

Visiting: 0

Edge: 0 → 1

0

1

2

3

Queue / Stack

1 - path: [0,1]2 - path: [0,2]

Visiting: 1

0

1

2

3

Queue / Stack

2 - path: [0,2]

Visiting: 1

Edge: 1 → 3

0

1

2

3

Queue / Stack

3 - path: [0,1,3]2 - path: [0,2]

Visiting: 1

0

1

2

3

Queue / Stack

3 - path: [0,1,3]2 - path: [0,2]

Visiting: 3

0

1

2

3

Queue / Stack

2 - path: [0,2]

Visiting: 3

0

1

2

3

Queue / Stack

2 - path: [0,2]

Visiting: 2

0

1

2

3

Visiting: 2

Edge: 2 → 3

0

1

2

3

Queue / Stack

3 - path: [0,2,3]

Visiting: 2

0

1

2

3

Queue / Stack

3 - path: [0,2,3]

Visiting: 3

0

1

2

3

Visiting: 3

0

1

2

3

Visiting: none

0

1

2

3

Key Takeaways

✓ Using an explicit stack with path tracking simulates DFS and finds all paths without recursion.

This is hard to see from code alone because recursion hides the path building and stack management.

✓ Stack order (LIFO) determines the order in which neighbors are explored and paths are built.

Visualizing stack pushes and pops clarifies why paths are discovered in a particular sequence.

✓ Paths are collected immediately upon reaching the target node, ensuring no unnecessary exploration beyond target.

Seeing when and how paths are added to results helps understand the stopping condition.

Practice

1. You are given a list of words sorted lexicographically in an unknown language. Your task is to determine the order of characters in this alien language. Which algorithmic approach guarantees an optimal solution to infer the character order from these constraints?

easy

A. Topological sort on a directed graph constructed from character precedence relations inferred from adjacent words

B. Greedy algorithm that picks the first differing character between adjacent words and orders them immediately

C. Dynamic programming to find the longest common subsequence between all pairs of words

D. Brute force comparison of all pairs of words to deduce character order by frequency

Solution

1. Step 1: Understand problem constraints

   The problem requires inferring a partial order of characters based on lexicographical ordering of words, which naturally forms a directed graph of precedence relations.

2. Step 2: Identify suitable algorithm

   Topological sort is the standard algorithm to find a linear order of nodes in a directed acyclic graph (DAG), which fits perfectly to infer character order from precedence edges.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Topological sort handles partial orders and cycles correctly [OK]

Hint: Partial order inference -> topological sort [OK]

Common Mistakes:

• Assuming greedy approach works without cycle detection
• Confusing longest common subsequence with order inference
• Using brute force frequency counts which ignore order

2. Consider the following Python code implementing the optimal leaf trimming approach for Minimum Height Trees. Given n = 4 and edges = [[1,0],[1,2],[1,3]], what is the final returned list?

easy

A. [3]

B. [0, 2, 3]

C. [2]

D. [1]

Solution

1. Step 1: Initialize graph and degrees

   Nodes: 0,1,2,3; edges connect 1 to 0,2,3. Degrees: 0->1, 1->3, 2->1, 3->1. Leaves initially: [0,2,3].

2. Step 2: Trim leaves until ≤ 2 nodes remain

   Remove leaves [0,2,3], decrement neighbors' degrees. Node 1 degree reduces from 3 to 0, becomes leaf. Remaining nodes = 4 - 3 = 1. Loop ends. Return [1].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only node 1 remains as centroid after trimming [OK]

Hint: Leaves trimmed until ≤2 nodes remain [OK]

Common Mistakes:

• Returning initial leaves
• Off-by-one in loop
• Not updating degrees correctly

3. What is the time complexity of the optimal leaf trimming algorithm for finding Minimum Height Trees in a tree with n nodes and n-1 edges?

medium

A. O(n²) because each leaf removal requires scanning all nodes.

B. O(n) because each edge and node is processed at most once during trimming.

C. O(n log n) due to priority queue operations for leaf selection.

D. O(n + m) where m is the number of edges, which equals n-1 here.

Solution

1. Step 1: Analyze leaf trimming operations

   Each node is added and removed from the leaves queue at most once. Each edge is visited when decrementing degrees.

2. Step 2: Combine node and edge processing

   Since the graph is a tree, edges = n-1. Total operations proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity matches leaf trimming algorithm [OK]

Hint: Each node and edge processed once [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing with BFS from each node
• Thinking priority queue is used

4. What is the time complexity of the optimal BFS-based topological sort algorithm for the Parallel Courses problem, given n courses and m prerequisite relations?

medium

A. O(n + m) because each node and edge is processed once in BFS

B. O(m^2) because updating indegrees requires scanning all edges repeatedly

C. O(n * m) because for each course you process all edges

D. O(n^2) because in the worst case all courses depend on all others

Solution

1. Step 1: Analyze graph traversal

   Each course (node) is enqueued and dequeued at most once; each edge is visited once when decrementing indegree.

2. Step 2: Combine node and edge processing

   Total operations proportional to number of nodes plus edges -> O(n + m).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in nodes and edges [OK]

Hint: Each edge and node processed once in BFS [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing indegree updates as repeated scans
• Assuming dense graph means O(n^2) always

5. Suppose the problem is modified so that elements in the sequences can be reused multiple times (i.e., sequences may contain repeated elements). Which of the following changes to the DFS postorder topological sort approach is necessary to correctly determine if the original sequence can be uniquely reconstructed?

hard

A. No changes needed; the existing DFS approach handles repeated elements naturally.

B. Modify graph construction to allow multiple edges between the same nodes and adjust cycle detection accordingly.

C. Switch to BFS topological sort with a queue that tracks in-degree counts considering repeated edges.

D. Preprocess sequences to remove duplicates before building the graph, then run the original DFS approach.

Solution

1. Step 1: Understand impact of repeated elements

   Repeated elements mean multiple edges between same nodes may exist, affecting graph structure and cycle detection.

2. Step 2: Adjust graph and DFS accordingly

   Graph must allow multiple edges or count edge multiplicity; cycle detection must consider these to avoid false negatives or infinite recursion.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Handling repeated edges is essential for correctness with reused elements [OK]

Hint: Repeated elements require multi-edge aware graph and cycle detection [OK]

Common Mistakes:

• Assuming no changes needed
• Removing duplicates loses info
• Switching to BFS without handling repeats