All Paths From Source to Target (DAG)

🎯

All Paths From Source to Target (DAG)

mediumGRAPHGoogleAmazonFacebook

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.

💡 This problem involves exploring all possible paths in a directed acyclic graph (DAG). Beginners often struggle because they confuse cycles with DAGs or don't realize that backtracking is needed to explore all paths.

📋

Problem Statement

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

💡

Example

Input"[[1,2],[3],[3],[]]"

Output[[0,1,3],[0,2,3]]

From node 0, you can go to 1 then 3, or 2 then 3, so two paths exist.

• Graph with only one node (0) → [[0]]
• Graph where source has no outgoing edges → []
• Graph with multiple branching paths → multiple paths returned
• Graph with long linear chain → single path from 0 to n-1

⚠️

Common Mistakes

Not backtracking path after recursion

Paths get corrupted with extra nodes, incorrect results

✅ Remove last node from path after recursive call (pop)

Not copying path when adding to results

All results reference same path object, leading to wrong outputs

✅ Add a copy of path (e.g., path[:], new ArrayList<>(path))

Assuming graph may have cycles without checks

Infinite recursion or stack overflow

✅ Confirm DAG property or add visited set to detect cycles

Not handling edge case of single node graph

Returns empty or incorrect paths

✅ Handle base case where source == target explicitly

Using recursion without memoization on large graphs

Time limit exceeded due to repeated work

✅ Add memoization to cache paths from nodes

🧠

Brute Force (Pure Recursion / Backtracking)

💡 This approach is the foundation for understanding how to explore all paths. It is simple but can be inefficient for large graphs due to repeated work and exponential path counts.

Intuition

Start from the source node and recursively explore all neighbors, building paths step-by-step until reaching the target node.

Algorithm

1. Initialize a result list to store all paths.
2. Define a recursive function that takes the current node and the path so far.
3. If the current node is the target, add the path to the result.
4. Otherwise, for each neighbor, recurse with the neighbor appended to the path.

💡 The recursion and backtracking can be tricky to visualize; it’s like exploring a tree of choices and returning when you hit a leaf.

</>

Code

from typing import List

def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
    res = []
    target = len(graph) - 1

    def dfs(node, path):
        if node == target:
            res.append(path[:])
            return
        for nei in graph[node]:
            path.append(nei)
            dfs(nei, path)
            path.pop()

    dfs(0, [0])
    return res

# Driver code
if __name__ == '__main__':
    graph = [[1,2],[3],[3],[]]
    print(allPathsSourceTarget(graph))

Line Notes

res = []Initialize list to collect all valid paths

target = len(graph) - 1Identify the target node index

def dfs(node, path):Define recursive DFS helper to explore paths

if node == target:Base case: reached target, add current path copy to results

for nei in graph[node]:Explore all neighbors of current node

path.append(nei)Add neighbor to current path before recursion

dfs(nei, path)Recursive call to continue path exploration

path.pop()Backtrack by removing last node to explore other paths

dfs(0, [0])Start DFS from source node with initial path

return resReturn all collected paths after DFS completes

import java.util.*;

public class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        int target = graph.length - 1;
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(0, target, graph, path, res);
        return res;
    }

    private void dfs(int node, int target, int[][] graph, List<Integer> path, List<List<Integer>> res) {
        if (node == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int nei : graph[node]) {
            path.add(nei);
            dfs(nei, target, graph, path, res);
            path.remove(path.size() - 1);
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = {{1,2},{3},{3},{}};
        System.out.println(sol.allPathsSourceTarget(graph));
    }
}

Line Notes

List<List<Integer>> res = new ArrayList<>();Initialize result list to store all paths

int target = graph.length - 1;Identify target node index

List<Integer> path = new ArrayList<>();Current path list to track nodes visited

path.add(0);Start path with source node

if (node == target)Base case: reached target node

res.add(new ArrayList<>(path));Add a copy of current path to results

for (int nei : graph[node])Iterate over neighbors of current node

path.add(nei);Add neighbor to path before recursion

dfs(nei, target, graph, path, res);Recursive DFS call

path.remove(path.size() - 1);Backtrack by removing last node

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        vector<int> path = {0};
        int target = graph.size() - 1;
        dfs(0, target, graph, path, res);
        return res;
    }

private:
    void dfs(int node, int target, vector<vector<int>>& graph, vector<int>& path, vector<vector<int>>& res) {
        if (node == target) {
            res.push_back(path);
            return;
        }
        for (int nei : graph[node]) {
            path.push_back(nei);
            dfs(nei, target, graph, path, res);
            path.pop_back();
        }
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> graph = {{1,2},{3},{3},{}};
    vector<vector<int>> paths = sol.allPathsSourceTarget(graph);
    for (auto &path : paths) {
        for (int node : path) cout << node << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<vector<int>> res;Stores all valid paths found

vector<int> path = {0};Initialize path with source node

int target = graph.size() - 1;Identify target node index

void dfs(int node, int target, vector<vector<int>>& graph, vector<int>& path, vector<vector<int>>& res)Recursive DFS helper function

if (node == target)Base case: reached target node

res.push_back(path);Add current path to results

for (int nei : graph[node])Iterate over neighbors of current node

path.push_back(nei);Add neighbor to path before recursion

dfs(nei, target, graph, path, res);Recursive DFS call

path.pop_back();Backtrack by removing last node

var allPathsSourceTarget = function(graph) {
    const res = [];
    const target = graph.length - 1;

    function dfs(node, path) {
        if (node === target) {
            res.push([...path]);
            return;
        }
        for (const nei of graph[node]) {
            path.push(nei);
            dfs(nei, path);
            path.pop();
        }
    }

    dfs(0, [0]);
    return res;
};

// Driver code
const graph = [[1,2],[3],[3],[]];
console.log(allPathsSourceTarget(graph));

Line Notes

const res = [];Initialize array to store all paths

const target = graph.length - 1;Identify target node index

function dfs(node, path)Recursive DFS helper function

if (node === target)Base case: reached target node

res.push([...path]);Add a copy of current path to results

for (const nei of graph[node])Iterate over neighbors of current node

path.push(nei);Add neighbor to path before recursion

dfs(nei, path);Recursive DFS call

path.pop();Backtrack by removing last node

⏱

Complexity

TimeO(2^n) in worst case due to exponential number of paths

SpaceO(n) recursion stack + O(2^n * n) for storing paths

Each node can branch to multiple neighbors, leading to exponential path counts; recursion stack depth is at most n.

💡 For n=20, this could mean millions of paths, making brute force impractical for large inputs.

Interview Verdict: Use only to introduce - not efficient for large inputs

This approach is easy to understand but too slow for big graphs; it helps build intuition.

🧠

DFS with Memoization (Caching Subpath Results)

💡 Memoization avoids recomputing paths from the same node multiple times, improving efficiency by caching results.

Intuition

Store all paths from each node to the target once computed, so if we revisit that node, we reuse the cached paths instead of recomputing.

Algorithm

1. Initialize a memo dictionary to map node to all paths from that node to target.
2. Define a recursive DFS function that returns all paths from current node to target.
3. If current node is target, return list containing path with only target.
4. If current node in memo, return cached paths.
5. Otherwise, for each neighbor, get all paths from neighbor to target, prepend current node, and collect.
6. Cache and return collected paths.

💡 Memoization changes the problem from exponential to polynomial by reusing results, but the recursion structure remains similar.

</>

Code

from typing import List

def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
    target = len(graph) - 1
    memo = {}

    def dfs(node):
        if node == target:
            return [[target]]
        if node in memo:
            return memo[node]
        paths = []
        for nei in graph[node]:
            for path in dfs(nei):
                paths.append([node] + path)
        memo[node] = paths
        return paths

    return dfs(0)

# Driver code
if __name__ == '__main__':
    graph = [[1,2],[3],[3],[]]
    print(allPathsSourceTarget(graph))

Line Notes

memo = {}Cache to store paths from nodes to target

def dfs(node):Recursive function returning all paths from node to target

if node == target:Base case: only one path from target to itself

if node in memo:Return cached paths if already computed

paths = []Collect all paths from current node

for nei in graph[node]:Explore neighbors

for path in dfs(nei):Get all paths from neighbor to target

paths.append([node] + path)Prepend current node to each path

memo[node] = pathsCache computed paths for current node

return pathsReturn all paths from current node

import java.util.*;

public class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int target = graph.length - 1;
        Map<Integer, List<List<Integer>>> memo = new HashMap<>();
        return dfs(0, target, graph, memo);
    }

    private List<List<Integer>> dfs(int node, int target, int[][] graph, Map<Integer, List<List<Integer>>> memo) {
        if (node == target) {
            List<List<Integer>> base = new ArrayList<>();
            base.add(new ArrayList<>(Arrays.asList(target)));
            return base;
        }
        if (memo.containsKey(node)) return memo.get(node);

        List<List<Integer>> paths = new ArrayList<>();
        for (int nei : graph[node]) {
            for (List<Integer> path : dfs(nei, target, graph, memo)) {
                List<Integer> newPath = new ArrayList<>();
                newPath.add(node);
                newPath.addAll(path);
                paths.add(newPath);
            }
        }
        memo.put(node, paths);
        return paths;
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = {{1,2},{3},{3},{}};
        System.out.println(sol.allPathsSourceTarget(graph));
    }
}

Line Notes

Map<Integer, List<List<Integer>>> memo = new HashMap<>();Cache to store paths from nodes to target

if (node == target)Base case: path from target to itself

if (memo.containsKey(node)) return memo.get(node);Return cached paths if available

List<List<Integer>> paths = new ArrayList<>();Collect all paths from current node

for (int nei : graph[node])Explore neighbors

for (List<Integer> path : dfs(nei, target, graph, memo))Get all paths from neighbor

List<Integer> newPath = new ArrayList<>();Create new path prepending current node

memo.put(node, paths);Cache computed paths

return paths;Return all paths from current node

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int target = graph.size() - 1;
        unordered_map<int, vector<vector<int>>> memo;
        return dfs(0, target, graph, memo);
    }

private:
    vector<vector<int>> dfs(int node, int target, vector<vector<int>>& graph, unordered_map<int, vector<vector<int>>>& memo) {
        if (node == target) {
            return {{target}};
        }
        if (memo.count(node)) return memo[node];

        vector<vector<int>> paths;
        for (int nei : graph[node]) {
            for (auto &path : dfs(nei, target, graph, memo)) {
                vector<int> newPath = {node};
                newPath.insert(newPath.end(), path.begin(), path.end());
                paths.push_back(newPath);
            }
        }
        memo[node] = paths;
        return paths;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> graph = {{1,2},{3},{3},{}};
    vector<vector<int>> paths = sol.allPathsSourceTarget(graph);
    for (auto &path : paths) {
        for (int node : path) cout << node << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

unordered_map<int, vector<vector<int>>> memo;Cache to store computed paths from nodes

if (node == target)Base case: path from target to itself

if (memo.count(node)) return memo[node];Return cached paths if available

vector<vector<int>> paths;Collect all paths from current node

for (int nei : graph[node])Explore neighbors

for (auto &path : dfs(nei, target, graph, memo))Get all paths from neighbor

vector<int> newPath = {node};Create new path starting with current node

newPath.insert(newPath.end(), path.begin(), path.end());Append neighbor's path

memo[node] = paths;Cache computed paths

return paths;Return all paths from current node

var allPathsSourceTarget = function(graph) {
    const target = graph.length - 1;
    const memo = new Map();

    function dfs(node) {
        if (node === target) return [[target]];
        if (memo.has(node)) return memo.get(node);

        const paths = [];
        for (const nei of graph[node]) {
            for (const path of dfs(nei)) {
                paths.push([node, ...path]);
            }
        }
        memo.set(node, paths);
        return paths;
    }

    return dfs(0);
};

// Driver code
const graph = [[1,2],[3],[3],[]];
console.log(allPathsSourceTarget(graph));

Line Notes

const memo = new Map();Cache to store paths from nodes to target

if (node === target) return [[target]];Base case: path from target to itself

if (memo.has(node)) return memo.get(node);Return cached paths if available

const paths = [];Collect all paths from current node

for (const nei of graph[node])Explore neighbors

for (const path of dfs(nei))Get all paths from neighbor

paths.push([node, ...path]);Prepend current node to each neighbor path

memo.set(node, paths);Cache computed paths

return paths;Return all paths from current node

⏱

Complexity

TimeO(V + E + P) where P is total number of paths

SpaceO(V * P * path_length) for memo and recursion stack

Memoization avoids recomputing paths, but all paths must still be stored and returned.

💡 This approach is much faster than brute force for graphs with overlapping subpaths.

Interview Verdict: Accepted - efficient for large DAGs with overlapping subpaths

Memoization is a key optimization that often turns exponential problems into manageable ones.

🧠

Iterative DFS with Explicit Stack and Path Tracking

💡 This approach uses an explicit stack to simulate recursion, which can be preferred in some languages or environments to avoid recursion limits.

Intuition

Use a stack to store pairs of (current node, path so far), iteratively exploring neighbors and building paths until the target is reached.

Algorithm

1. Initialize a stack with a tuple containing source node and path [0].
2. While stack not empty, pop top element (node, path).
3. If node is target, add path to results.
4. Otherwise, push neighbors with updated paths onto stack.
5. Return all collected paths.

💡 Tracking paths explicitly on the stack can be tricky but avoids recursion overhead.

</>

Code

from typing import List

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

    while stack:
        node, path = stack.pop()
        if node == target:
            res.append(path)
        else:
            for nei in graph[node]:
                stack.append((nei, path + [nei]))
    return res

# Driver code
if __name__ == '__main__':
    graph = [[1,2],[3],[3],[]]
    print(allPathsSourceTarget(graph))

Line Notes

stack = [(0, [0])]Initialize stack with source node and path

while stack:Process nodes until stack is empty

node, path = stack.pop()Pop current node and path to explore

if node == target:If target reached, add path to results

for nei in graph[node]:Push neighbors with updated paths onto stack

stack.append((nei, path + [nei]))Create new path including neighbor

import java.util.*;

public class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int target = graph.length - 1;
        List<List<Integer>> res = new ArrayList<>();
        Deque<Pair<Integer, List<Integer>>> stack = new ArrayDeque<>();
        stack.push(new Pair<>(0, new ArrayList<>(Arrays.asList(0))));

        while (!stack.isEmpty()) {
            Pair<Integer, List<Integer>> curr = stack.pop();
            int node = curr.getKey();
            List<Integer> path = curr.getValue();
            if (node == target) {
                res.add(path);
            } else {
                for (int nei : graph[node]) {
                    List<Integer> newPath = new ArrayList<>(path);
                    newPath.add(nei);
                    stack.push(new Pair<>(nei, newPath));
                }
            }
        }
        return res;
    }

    // Helper Pair class
    static class Pair<K,V> {
        private K key;
        private V value;
        public Pair(K key, V value) { this.key = key; this.value = value; }
        public K getKey() { return key; }
        public V getValue() { return value; }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] graph = {{1,2},{3},{3},{}};
        System.out.println(sol.allPathsSourceTarget(graph));
    }
}

Line Notes

Deque<Pair<Integer, List<Integer>>> stack = new ArrayDeque<>();Stack to hold nodes and paths for iterative DFS

stack.push(new Pair<>(0, new ArrayList<>(Arrays.asList(0))));Initialize stack with source node and path

while (!stack.isEmpty())Process until stack is empty

Pair<Integer, List<Integer>> curr = stack.pop();Pop current node and path

if (node == target)If target reached, add path to results

for (int nei : graph[node])Push neighbors with updated paths

List<Integer> newPath = new ArrayList<>(path);Copy current path to extend

stack.push(new Pair<>(nei, newPath));Push neighbor and new path onto stack

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int target = graph.size() - 1;
        vector<vector<int>> res;
        stack<pair<int, vector<int>>> stk;
        stk.push({0, {0}});

        while (!stk.empty()) {
            auto [node, path] = stk.top();
            stk.pop();
            if (node == target) {
                res.push_back(path);
            } else {
                for (int nei : graph[node]) {
                    vector<int> newPath = path;
                    newPath.push_back(nei);
                    stk.push({nei, newPath});
                }
            }
        }
        return res;
    }
};

// Driver code
int main() {
    Solution sol;
    vector<vector<int>> graph = {{1,2},{3},{3},{}};
    vector<vector<int>> paths = sol.allPathsSourceTarget(graph);
    for (auto &path : paths) {
        for (int node : path) cout << node << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

stack<pair<int, vector<int>>> stk;Stack to hold nodes and paths for iterative DFS

stk.push({0, {0}});Initialize stack with source node and path

while (!stk.empty())Process until stack is empty

auto [node, path] = stk.top();Pop current node and path

if (node == target)If target reached, add path to results

for (int nei : graph[node])Push neighbors with updated paths

vector<int> newPath = path;Copy current path to extend

newPath.push_back(nei);Add neighbor to new path

stk.push({nei, newPath});Push neighbor and new path onto stack

var allPathsSourceTarget = function(graph) {
    const target = graph.length - 1;
    const res = [];
    const stack = [[0, [0]]];

    while (stack.length > 0) {
        const [node, path] = stack.pop();
        if (node === target) {
            res.push(path);
        } else {
            for (const nei of graph[node]) {
                stack.push([nei, [...path, nei]]);
            }
        }
    }
    return res;
};

// Driver code
const graph = [[1,2],[3],[3],[]];
console.log(allPathsSourceTarget(graph));

Line Notes

const stack = [[0, [0]]]Initialize stack with source node and path

while (stack.length > 0)Process until stack is empty

const [node, path] = stack.pop();Pop current node and path

if (node === target)If target reached, add path to results

for (const nei of graph[node])Push neighbors with updated paths

stack.push([nei, [...path, nei]]);Create new path including neighbor and push

⏱

Complexity

TimeO(2^n) in worst case due to number of paths

SpaceO(n * 2^n) for stack and storing paths

Iterative DFS explores all paths similarly to recursion but avoids call stack overhead.

💡 This approach is useful when recursion depth is limited or iterative style is preferred.

Interview Verdict: Accepted - alternative to recursive DFS

Iterative DFS is a good fallback if recursion is problematic or disallowed.

📊

All Approaches - One-Glance Tradeoffs

💡 Memoized DFS is the best balance of clarity and efficiency for most interviews; iterative DFS is a good alternative if recursion is limited.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n) worst case	O(n) recursion stack + O(2^n * n) paths	Yes (deep recursion)	Yes	Mention only - never code for large inputs
2. DFS with Memoization	O(V + E + P) where P is total paths	O(V * P * path_length) for memo and stack	Yes (deep recursion)	Yes	Code this approach in 95% of interviews
3. Iterative DFS with Stack	O(2^n) worst case	O(n * 2^n) for stack and paths	No	Yes	Use if recursion depth is a concern

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, optimize with memoization, and optionally discuss iterative DFS.

How to Present

Step 1: Clarify the problem and constraints, confirm graph is a DAG.Step 2: Describe brute force recursive DFS to find all paths.Step 3: Explain inefficiency and introduce memoization to cache results.Step 4: Optionally mention iterative DFS to avoid recursion.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests understanding of DFS, backtracking, memoization, and ability to handle path reconstruction and large inputs.

Common Follow-ups

• What if the graph contains cycles? → Detect cycles and avoid infinite loops.
• How to optimize if only count of paths is needed? → Use DP counting instead of storing paths.

💡 These follow-ups test your ability to adapt the solution to variations and optimize further.

🔍

Pattern Recognition

When to Use

1) Problem asks for all paths from source to target; 2) Graph is directed and acyclic; 3) Need to enumerate paths, not just count; 4) Backtracking or DFS is suggested.

Signature Phrases

all paths from source to targetdirected acyclic graphreturn all possible paths

NOT This Pattern When

Shortest path problems (use BFS/Dijkstra), cycle detection (use DFS with visited sets)

Similar Problems

Number of Paths in DAG - counts paths instead of listingFind All Paths in Maze - similar backtracking approachLongest Path in DAG - uses topological order but different goal

Practice

1. Given the following Python code snippet implementing the optimal alien dictionary solution, what is the final returned order for the input words = ["wrt", "wrf", "er", "ett", "rftt"]?

from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nei in graph[c]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) < len(in_degree):
        return ""
    return "".join(order)

print(alienOrder(words))

easy

A. "wretf"

B. "wertf"

C. "wert"

D. "wrtef"

Solution

1. Step 1: Build graph and in-degree map

   Edges: w->e, e->r, r->t, t->f. In-degree counts: w=0, e=1, r=1, t=1, f=1.

2. Step 2: Perform BFS topological sort

   Start with 'w' (in-degree 0), then 'e', 'r', 't', 'f' in order as their in-degree drops to zero.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order "wertf" respects all precedence edges [OK]

Hint: Trace BFS queue and in-degree updates [OK]

Common Mistakes:

• Stopping early and missing characters
• Misordering characters with same in-degree
• Ignoring prefix invalid case

2. You are given a list of courses and their prerequisite pairs. You need to find an order to take all courses such that all prerequisites are satisfied. Which algorithmic approach guarantees an optimal solution to determine such an order if it exists?

easy

A. Use a greedy algorithm that always picks the course with the fewest prerequisites next.

B. Use a topological sort algorithm based on BFS and in-degree counting (Kahn's Algorithm).

C. Use dynamic programming to build up solutions from smaller subproblems.

D. Use backtracking to try all permutations of courses and check prerequisites.

Solution

1. Step 1: Understand the problem as a graph

   Courses and prerequisites form a directed graph where edges represent dependencies.

2. Step 2: Identify the algorithm that finds a linear ordering respecting dependencies

   Kahn's Algorithm uses BFS and in-degree counts to find a topological order efficiently and detects cycles.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Topological sort with BFS is the standard approach for course scheduling [OK]

Hint: Topological sort with BFS handles prerequisites and cycles [OK]

Common Mistakes:

• Thinking greedy approach always works
• Confusing DP with topological ordering
• Trying all permutations is too slow

3. What is the time complexity of the optimal alien dictionary solution using BFS topological sort on the graph constructed from the input words, where C is the total number of characters in all words, U is the number of unique characters, and E is the number of edges in the graph?

medium

A. O(C * U * E) due to nested loops over characters and edges

B. O(C^2) because all pairs of characters are compared in the worst case

C. O(U^2) since each character can be compared with every other character

D. O(C + U + E) because building the graph and BFS traversal each take linear time in input size and graph size

Solution

1. Step 1: Analyze graph construction

   Building graph edges requires comparing adjacent words once, total O(C) characters processed.

2. Step 2: Analyze BFS topological sort

   Traversal visits each node (U) and edge (E) once, total O(U + E).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sum of graph build and BFS traversal is O(C + U + E) [OK]

Hint: Graph build + BFS traversal linear in input and graph size [OK]

Common Mistakes:

• Assuming quadratic complexity due to pairwise comparisons
• Ignoring that edges are at most U^2 but usually less
• Confusing total characters with unique characters

4. The following code attempts to find the longest path with different adjacent characters in a DAG. Identify the line containing the subtle bug that causes incorrect results on graphs with cycles or repeated characters.

medium

A. Line with 'for node in topo_order:' loop

B. Line with 'dp = [1] * n' initialization

C. Line with 'if indegree[nei] <= 0:' condition

D. Line with 'return max(dp)' statement

Solution

1. Step 1: Analyze indegree decrement and queue append

   The condition 'if indegree[nei] <= 0:' incorrectly allows nodes with negative indegree to be enqueued multiple times, breaking topological order.

2. Step 2: Consequence of bug

   This causes incorrect topo_order and potentially infinite loops or wrong dp updates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct condition should be 'indegree[nei] == 0' to enqueue once [OK]

Hint: Check indegree condition carefully for cycle detection [OK]

Common Mistakes:

• Using <= 0 instead of == 0 for indegree check
• Ignoring character difference in dp update
• Incorrect dp initialization

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