Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Course Schedule

Graphsmedium

Given `numCourses` and a `prerequisites` list of `[course, dependsOn]` pairs, implement `canFinish(numCourses, prerequisites)` returning whether all courses can be completed (the dependency graph has no cycle).

Sample tests

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

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Confusing the edge direction between course and prerequisite.

Learning resources

  • Wikipedia: Graph traversal
Approach & explanation (try first)

Kahn's topological sort finishes all courses only if there is no cycle. O(V + E) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.