The O(n) Club: All Paths in a DAG (aka How Many Ways Can You Get Lost Without Ever Looping Back?)

The O(n) Club: All Paths in a DAG (aka How Many Ways Can You Get Lost Without Ever Looping Back?)

⚡ TL;DR

You’re handed a Directed Acyclic Graph (DAG) as an adjacency list. Your not-at-all-annoying task? Find every possible path (in order) from node 0 to node n-1. Recursion + backtracking (DFS) is your caffeine-fueled friend. Here’s the elevator-pitch snippet:

// Simple DFS with backtracking in Java
void dfs(int[][] graph, List<list>> allPaths, List<integer> path, int node) {
    path.add(node);
    if(node == graph.length - 1) allPaths.add(new ArrayList<>(path));
    else for(int next: graph[node]) dfs(graph, allPaths, path, next);
    path.remove(path.size()-1);
}
</integer></list>

🧠 How Devs Usually Mess This Up

If your gut says ‘add a visited[] array!’. Stop. Put down the keyboard. In a DAG, cycles are banished by definition. You do not need to track revisits—you’re safe unless you just like inventing busywork. Another classic fail: stopping after the first path or counting instead of collecting. Or returning node values like you’re collecting baseball cards, not actual routes. The real world (aka the interviewer) wants all possible journey maps, not a headcount or breadcrumbs to nowhere.

🔍 What’s Actually Going On

Picture a gigantic, one-way office building. No trapdoors, no elevators dumping you on the same floor. You enter at door 0, and your mission (should you not want your coffee confiscated): record every distinct legal route to the CEO’s penthouse suite (node n-1). You can only move forward, you may have to backtrack when you run out of options, and there is absolutely, positively no secret staircase leading you in a loop. When you reach the penthouse, jot your path, rewind, and try a new branch: you are a very overworked, forgetful courier bot.

🛠️ PseudoCode

• Prepare a list to hold all paths.
  List<List<Integer>> allPaths = new ArrayList<>();
• Kick off DFS from node 0 with an empty path:
  dfs(graph, allPaths, new ArrayList<>(), 0);
• DFS Routine (each step):
  • Add current node to your path (because you got here and that’s worth something).
  • If it’s the last stop (n-1), add a fresh copy of path to allPaths.
  • Otherwise, for every neighbor, call DFS recursively with that neighbor. Ignore cycle paranoia—DAG has your back.
  • After exploring, backtrack: remove the current node so other routes don’t hallucinate.
• Finish by returning allPaths. (High five, you’re done!)

💻 The Code

import java.util.*;
 public class AllPathsDAG {
    public List<list>> allPathsSourceTarget(int[][] graph) {
        List<list>> res = new ArrayList<>();
        List
<integer> path = new ArrayList<>();
        dfs(graph, 0, path, res);
        return res;
    }
    private void dfs(int[][] graph, int node, List
<integer> path, List<list>> res) {
        path.add(node);
        if(node == graph.length - 1) {
            res.add(new ArrayList<>(path)); // Grab a shiny new copy!
        } else {
            for(int next : graph[node]) {
                dfs(graph, next, path, res);
            }
        }
        path.remove(path.size()-1); // Backtrack to reality
    }
}
</list></integer></integer></list></list>

⚠️ Pitfalls, Traps & Runtime Smacks

• DO NOT track visited nodes. No cycles, no scapegoats.
• If you forget new ArrayList<>(path) when storing a finished path, get ready for a tragic recursion slideshow—the same list will mutate on you.
• If your graph has tons of split branches, the output can reach “spaghetti junction” size. Don’t say we didn’t warn you.
• Complexity Check: Both time and space = number of possible paths x avg path length. If your DAG is secretly a lattice of doom, pour more coffee.

🧠 Interviewer Brain-Tattoo

“Acyclic means never loop, always copy your list, and if you write a visited[] here, a puppy cries somewhere in Mountain View.”