AlgoLounge

Course Schedule

medium

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ᵢ.

  • For example, the pair [0, 1] indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Examples

Example 1

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: true

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= aᵢ, bᵢ < numCourses
  • All the pairs prerequisites[i] are unique.
TypeScript
Loading editor…
List of test cases (10)
Case 1
numCourses = 2
prerequisites = [[1,0]]
Case 2
numCourses = 2
prerequisites = [[1,0],[0,1]]
Case 3
numCourses = 1
prerequisites = []
Case 4
numCourses = 4
prerequisites = [[1,0],[2,1],[3,2]]
Case 5
numCourses = 3
prerequisites = [[0,1],[1,2],[2,0]]
Case 6
numCourses = 6
prerequisites = [[1,0],[2,1],[4,3]]
Case 7
numCourses = 5
prerequisites = [[1,0],[0,1],[3,2]]
Case 8
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Case 9
numCourses = 1
prerequisites = [[0,0]]
Case 10
numCourses = 8
prerequisites = [[2,0],[2,1],[3,1],[4,2],[5,2],[6,3],[6,4],[7,5],[7,6]]