Bird
Raised Fist0

What is the space complexity of the iterative DFS approach that stores all paths from source to target in a DAG with n nodes and P paths?

medium🪤 Complexity Trap Q6 of Q15
Topological Sort - All Paths From Source to Target (DAG)
What is the space complexity of the iterative DFS approach that stores all paths from source to target in a DAG with n nodes and P paths?
AO(n)
BO(n * P)
CO(P^2)
DO(n + P)
Step-by-Step Solution
Solution:
  1. Step 1: Consider space for stack and paths

    Stack stores partial paths, each up to length n, and total paths P.
  2. Step 2: Calculate total space

    Storing all paths requires O(n * P) space; stack overhead is proportional to path length times number of paths.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Space grows linearly with number of paths and path length [OK]
Quick Trick: Space includes all paths and stack overhead [OK]
Common Mistakes:
MISTAKES
  • Ignoring path length in space
  • Assuming linear space only
Trap Explanation:
PITFALL
  • Candidates often forget that storing all paths requires space proportional to path length times number of paths.
Interviewer Note:
CONTEXT
  • Tests understanding of space complexity including auxiliary data structures.
Master "All Paths From Source to Target (DAG)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes