Course Schedule
Medium
Depth-First Search
Breadth-First Search
Graph
Topological Sort
There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [aᵢ, bᵢ]` indicates that you must take course `bᵢ` first if you want to take course `aᵢ`. Return `true` *if you can finish all courses. Otherwise, return* `false`.
Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Example 3
Input: numCourses = 1, prerequisites = []
Output: true

Constraints

  • •1 <= numCourses <= 2000
  • •0 <= prerequisites.length <= 5000
  • •prerequisites[i].length == 2
  • •0 <= aᵢ, bᵢ < numCourses
  • •All the pairs prerequisites[i] are unique.
Time Complexity
O(V+E)
Space Complexity
O(V+E)
14
Case 1
Input: 2 [[1,0]]
Expected: true
Case 2
Input: 2 [[1,0],[0,1]]
Expected: false
Case 3
Input: 1 []
Expected: true