Bird
Raised Fist0

What is the space complexity of the optimal BFS topological sort solution for the Parallel Courses problem with n courses and m prerequisite relations?

medium🪤 Complexity Trap Q6 of Q15
Topological Sort - Parallel Courses (Minimum Semesters)
What is the space complexity of the optimal BFS topological sort solution for the Parallel Courses problem with n courses and m prerequisite relations?
AO(n^2) due to adjacency matrix storage
BO(m) for storing edges only
CO(n) only for indegree array and queue
DO(n + m) for graph adjacency list, indegree array, and queue
Step-by-Step Solution
Solution:
  1. Step 1: Identify data structures used

    Adjacency list uses O(n + m) space; indegree array uses O(n); queue uses O(n).
  2. Step 2: Consider adjacency matrix variant

    Adjacency matrix uses O(n^2) space, but the optimal solution uses adjacency list.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Adjacency list plus arrays and queue require O(n + m) space [OK]
Quick Trick: Adjacency list -> O(n + m) space; adjacency matrix -> O(n^2) [OK]
Common Mistakes:
MISTAKES
  • Forgetting queue space
  • Ignoring adjacency list usage
Trap Explanation:
PITFALL
  • Candidates often confuse adjacency matrix and list space complexities.
Interviewer Note:
CONTEXT
  • Tests awareness of space trade-offs in graph representations.
Master "Parallel Courses (Minimum Semesters)" 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