Bird
Raised Fist0

What is the space complexity of the optimal approach (reverse graph + Kahn's algorithm) for finding eventual safe states in a graph with V nodes and E edges?

medium🪤 Complexity Trap Q6 of Q15
Topological Sort - Find Eventual Safe States
What is the space complexity of the optimal approach (reverse graph + Kahn's algorithm) for finding eventual safe states in a graph with V nodes and E edges?
AO(V)
BO(V + E)
CO(E)
DO(V^2)
Step-by-Step Solution
Solution:
  1. Step 1: Analyze auxiliary data structures

    The reversed graph stores all edges, requiring O(E) space.
  2. Step 2: Additional arrays

    In-degree and queue use O(V) space, so total space is O(V + E).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Space dominated by nodes and edges stored in reversed graph and arrays [OK]
Quick Trick: Reversed graph edges and node arrays dominate space [OK]
Common Mistakes:
MISTAKES
  • Ignoring node array space
  • Assuming only edge storage counts
Trap Explanation:
PITFALL
  • Candidates often forget node arrays contribute to space complexity along with edges.
Interviewer Note:
CONTEXT
  • Checks understanding of total space usage in graph algorithms.
Master "Find Eventual Safe States" 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