There are numCourses courses. Each pair [a, b] means b must be taken before a. Return whether it is possible to finish every course.
Before you code
All courses can be finished exactly when the prerequisite graph has no cycle, which is exactly when a topological order exists.
Hints
- Add an edge b → a for each pair and count in-degrees.
- Run Kahn's algorithm and count how many courses are output.
- Return whether that count equals numCourses.
Production & complexity notes
When solving Course schedule on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Topological sort to reinforce the underlying pattern.
What it practices
Kahn's algorithm as a cycle test, from Topological sort.