Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Course Schedule

Graphsmedium

There are `numCourses` courses labeled `0` to `numCourses - 1`. `prerequisites[i] = [a, b]` means you must take `b` before `a`. Implement `canFinish(numCourses, prerequisites)` returning `true` if you can finish every course, `false` if a cycle makes it impossible. (Asked at Amazon and Google.)

Examples

Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Take course 0, then course 1.
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
0 and 1 depend on each other — a cycle.

Sample tests

Input: canFinish(2, [[1,0]])
Output: true
Input: canFinish(2, [[1,0],[0,1]])
Output: false

+ 2 hidden tests run on Submit.

Hints

Common pitfalls
  • Confusing edge direction — `[a, b]` means an edge from b to a (b unlocks a).
  • Concluding success without checking that every course was processed; a leftover cycle never reaches in-degree 0.

Learning resources

  • Wikipedia: Topological sorting
Approach & explanation (try first)

Finishing all courses is possible exactly when the prerequisite graph is a DAG. Kahn's algorithm tracks in-degrees, starts from prerequisite-free courses, and peels the graph layer by layer. If the number processed equals `numCourses`, no cycle exists. O(V + E).

Loading...
⌘/Ctrl + Enter

Run your code to see results.