Course Schedule
Decide whether all courses can be completed given prerequisite edges.
Why does this pattern fit?
Restate the exact job
Decide whether all courses can be completed given prerequisite edges.
A directed cycle is exactly the obstruction to a valid order.
O(V + E) time · O(V + E) space
Reversing prerequisite edge direction produces the wrong dependencies.
How to solve Course Schedule
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Decide whether all courses can be completed given prerequisite edges.
Why Graphs: traversal & ordering fits
A directed cycle is exactly the obstruction to a valid order.
State to maintain
Indegrees plus a queue of zero-indegree courses.
Transition
Remove available courses, decrement outgoing indegrees, and compare processed count with total.
Time and space
O(V + E) time · O(V + E) space
Counterexample to the tempting mistake
Reversing prerequisite edge direction produces the wrong dependencies.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.