You are given a total of n courses labeled 0 to n-1, and a list of prerequisite pairs. Each pair [a, b] means you must complete course b before course a. Determine if it is possible to finish all courses.
For example:
n = 4, prerequisites = [[1,0], [2,1], [3,2]]
This is possible: take courses in order 0, 1, 2, 3.
n = 2, prerequisites = [[0,1], [1,0]]
This is impossible: course 0 requires course 1, and course 1 requires course 0 (circular dependency).
What graph concept does this map to? How do you detect the impossible case?
Explain your approach and analyze the time and space complexity.
How to approach it
- Hint 1
Model this as a directed graph where an edge from b to a means b is a prerequisite for a. The question is whether this graph has a valid topological ordering.
- Hint 2
A valid topological ordering exists if and only if the graph has no cycles.
- Hint 3
Use Kahn's algorithm (BFS): start with nodes that have no prerequisites (in-degree 0). Process them, reduce in-degrees of their dependents, and repeat. If all nodes are processed, no cycle exists.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.